\documentstyle[jair,fleqn,twoside,11pt,theapa,epsf]{article}

\jairheading{2}{1995}{575-609}{12/94}{5/95}
\ShortHeadings{Provably bounded-optimal agents}{Russell \& Subramanian}
\firstpageno{575}

\begin{document}
\sloppy
\title{Provably Bounded-Optimal Agents} 

\author{\name Stuart J. Russell 
         \email russell@cs.berkeley.edu \\
        \addr Computer Science Division, University of California \\
              Berkeley, CA 94720, USA 
        \AND
        \name  Devika Subramanian 
        \email devika@cs.cornell.edu \\
        \addr  Computer Science Department, Cornell University \\
               Ithaca, NY 14853, USA 
               }

\maketitle

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

\def\resettheoremcounters{\setcounter{\c@theorem}{0}
\setcounter{\c@lemma}{0}
\setcounter{\c@proposition}{0}
\setcounter{\c@definition}{0}
\setcounter{\c@corollary}{0}}


\def\action{{\rm action}}
\def\argmax{{\rm argmax}}
\def\fopt{f_{{\rm opt}}}
\def\lopt{l_{{\rm opt}}}
\def\Qopt{Q_{{\rm opt}}}
\def\qopt{q_{{\rm opt}}}
\def\topt{t_{{\rm opt}}}
\def\effects{\mbox{\it effects}}
\def\tb{\phantom{abcd}}

\def\wT{T^*}
\def\wV{V^*}
\def\wQ{Q^*}

\def\R{\mbox{\bf R}}
\def\E{\mbox{\bf E}}
\def\T{\mbox{\bf T}}
\def\O{\mbox{\bf O}}
\def\I{\mbox{\bf I}}
\def\A{\mbox{\bf A}}
\def\X{\mbox{\bf X}}

\def\smallR{\mbox{\scriptsize\bf R}}
\def\smallE{\mbox{\scriptsize\bf E}}
\def\smallT{\mbox{\scriptsize\bf T}}

\def\at{A^t}
\def\aT{A^{\smallT}}
\def\AT{\mbox{\bf A}^{\smallT}}
\def\At{\mbox{\bf A}^t}
\def\Abot{\mbox{\bf A}_{\bot}}
 
\def\pt{O^t}
\def\pT{O^{\smallT}}
\def\PT{\mbox{\bf O}^{\smallT}}
\def\Pt{\mbox{\bf O}^t}
\def\od{O_d}
\def\xt{X^t}
\def\xT{X^{\smallT}}
\def\XT{\mbox{\bf X}^{\smallT}}
\def\Xt{\mbox{\bf X}^t}

\def\jt{I^t}
\def\iT{I^{\smallT}}
\def\IT{\mbox{\bf I}^{\smallT}}
\def\It{\mbox{\bf I}^t}



\begin{abstract}

Since its inception, artificial intelligence has relied upon a
theoretical foundation centred around {\em perfect rationality} as the
desired property of intelligent systems. We argue, as others have
done, that this foundation is inadequate because it imposes
fundamentally unsatisfiable requirements. As a result, there has
arisen a wide gap between theory and practice in AI, hindering
progress in the field. We propose instead a property called {\em
bounded optimality}. Roughly speaking, an agent is bounded-optimal if
its program is a solution to the constrained optimization problem
presented by its architecture and the task environment. We show how to
construct agents with this property for a simple class of machine
architectures in a broad class of real-time environments. We
illustrate these results using a simple model of an automated mail
sorting facility.  We also define a weaker property, {\em asymptotic
bounded optimality} (ABO), that generalizes the notion of optimality in classical complexity theory.
We then construct {\em
universal} ABO programs, i.e., programs that are ABO no matter what real-time constraints
are applied.  Universal ABO programs can be used as building
blocks for more complex systems. We conclude with a discussion of the
prospects for bounded optimality as a theoretical basis for AI, and
relate it to similar trends in philosophy, economics, and game theory.



\end{abstract}

\section{Introduction}\label{intro-section}

Since before the beginning of artificial intelligence, philosophers,
control theorists
and economists have looked for a satisfactory definition of rational
behaviour. This is needed to  underpin theories of ethics, inductive
learning, reasoning, optimal control, decision-making, and economic modelling.
Doyle (1983) has proposed that AI itself be
defined as the computational study of rational behaviour---effectively
equating rational behaviour with intelligence. The role of
such definitions in AI is to ensure that theory and practice are
correctly aligned. If we define some 
property $P$, then we hope to be able to design a system
that provably possesses property $P$. Theory meets practice when our
systems exhibit $P$ in reality. Furthermore, that they exhibit $P$ in
reality should be something that we actually care about.  In a sense,
the choice of what $P$ to study determines the nature of
the field.
%[[keep this??]] We should
%also be able to use such a 
%definition to design more complex systems without worrying about
%implementation details of the components. 

There are a number of possible choices for $P$:
\vspace{-.05in}
\begin{itemize}
\item {\em Perfect rationality}: the classical notion of rationality
  in economics and philosophy. A perfectly rational agent acts at every
  instant in such a way as to maximize its expected utility, given the
  information it has acquired from the environment.  Since action
  selection requires computation, and computation takes time, perfectly
  rational agents do not exist for non-trivial environments.

\item {\em Calculative rationality}: the notion of rationality studied
  in AI. A calculatively rational agent eventually returns what would
  have been the rational choice at the beginning of its deliberation.
  There exist systems such as influence diagram evaluators that exhibit
  this property for a decision-theoretic definition of rational choice,
  and systems such as nonlinear planners that exhibit it for a logical
  definition of rational choice. This is assumed to be an interesting
  property for a system to exhibit since it constitutes an
  ``in-principle'' capacity to do the right thing. Calculative
  rationality is of limited value in practice, because the actual
  behaviour exhibited by such systems is absurdly far from being
  rational; for example, a calculatively rational chess program will
  choose the right move, but may take $10^{50}$ times too long to do so.
  As a result, AI system-builders often ignore theoretical developments,
  being forced to rely on trial-and-error engineering to achieve their
  goals. Even in simple domains such as chess, there is little theory for
  designing and analysing high-performance programs.
  
\item {\em Metalevel rationality}: a natural response to the problems
  of calculative rationality. A metalevel rational system optimizes
over the object-level computations to be performed in the service of
selecting actions. In other words, for each decision it finds the
  optimal combination of computation-sequence-plus-action, under the constraint
  that the action must be selected by the computation.
Full metalevel rationality is seldom useful because the metalevel
computations themselves take time, and the metalevel decision problem
is often more difficult than the object-level problem.
Simple approximations to metalevel rationality have proved useful in
practice---for example, metalevel policies that limit lookahead in
chess programs---but these engineering expedients merely serve to
illustrate the lack of a theoretical basis for agent design.
        
\item {\em Bounded optimality}: a bounded optimal agent behaves as
  well as possible given its computational resources.  Bounded
  optimality specifies optimal {\em programs} rather than optimal {\em
  actions} or optimal {\em computation sequences}.  Only by the former
  approach can we avoid placing constraints on intelligent agents that
  cannot be met by any program.  Actions and computations are, after
  all, generated by programs, and it is over programs that designers have
  control.
\end{itemize}

We make three claims:
\begin{enumerate}
\item A system that exhibits bounded optimality is desirable in
  reality.
\item It is possible to construct provably bounded optimal programs.
\item Artificial intelligence can be usefully characterized as the
  study of bounded optimality, particularly in the context of complex
  task environments and reasonably powerful computing devices.
\end{enumerate}
The first claim is unlikely to be controversial. This paper
supports the second claim in detail. The third claim may, or may not,
stand the test of time.

We begin in section~\ref{history-section} with a necessarily brief
discussion of the relationship between bounded optimality and earlier
notions of rationality. We note in particular that some important
distinctions can be missed without precise definitions of terms.  Thus
in section~\ref{agents-section} we provide formal definitions of
agents, their programs, their behaviour and their rationality.
Together with formal descriptions of task environments, these elements
allow us to prove that a given agent exhibits bounded optimality.
Section~\ref{bo-section} examines a class of agent architectures for
which the problem of generating bounded optimal configurations is
efficiently soluble. The solution involves a class of interesting and
practically relevant optimization problems that do not appear to have
been addressed in the scheduling literature.  We illustrate the
results by showing how the throughput  of an automated
mail-sorting facility might be improved.
Section~\ref{learning-section} initiates a discussion of how bounded
optimal configurations might be learned from experience in an
environment. In section~\ref{abo-section}, we define a weaker
property, {\em asymptotic bounded optimality} (ABO), that may be more
robust and tractable than the strict version of bounded optimality. In
particular, we can construct {\em universal} ABO programs.  A program
is universally ABO if it is ABO regardless of the specific form of
time dependence of the utility function.\footnote{This usage of the
  term ``universal'' derives from its use in the scheduling of
  randomized algorithms by Luby, Sinclair and Zuckerman (1993).} Universal ABO programs
can therefore be used as building blocks for more complex systems. We
conclude with an assessment of the prospects for further development
of this approach to artificial intelligence.



\section{Historical Perspective}\label{history-section}
 
The classical idea of perfect rationality, which developed from
Aristotle's theories of ethics, work by Arnauld and others on choice
under uncertainty, and Mill's utilitarianism, was put on a formal
footing in {\em decision theory} by Ramsey (1931) and vonNeumann and
Morgernstern (1947). It stipulates that a rational agent always act so
as to maximize its {\em expected} utility. The expectation is taken
according to the agent's own beliefs; thus, perfect rationality does
not require omniscience.


In artificial intelligence, the logical definition of rationality,
known in philosophy as the ``practical syllogism'', was put forward by
McCarthy (1958), and reiterated strongly by
Newell (1981). Under this definition, an agent
should take any action that it believes is guaranteed to achieve any
of its goals. If AI can be said to have had a theoretical foundation,
then this definition of rationality has provided it. 
McCarthy
believed, probably correctly, that in the early
stages of the field it was important to concentrate on
``epistemological adequacy'' before ``heuristic adequacy'' --- that
is, capability in principle rather than in practice.  
The methodology that has resulted involves designing programs that
exhibit calculative rationality, and then using various speedup
techniques and approximations in the hope of getting as close as
possible to perfect rationality. Our belief, albeit unproven, is that
the simple agent designs that fulfill the specification of calculative
rationality may not provide good starting points from which to
approach bounded optimality. Moreover, a theoretical foundation based
on calculative rationality cannot provide the necessary guidance in
the search.

It is not clear that AI would have embarked on the quest for
calculative rationality had it not been operating in the halcyon days
before formal intractability results were discovered.
One response to the spectre of complexity has been to rule
it out of bounds.  Levesque and Brachman (1987)
suggest limiting the complexity of the environment so that calculative and
perfect rationality coincide. Doyle and Patil (1991)
argue strongly against this position.



Economists have used perfect rationality as an abstract model of
economic entities, for the purposes of economic forecasting and
designing market mechanisms. This makes it possible to prove 
theorems about the properties of markets in equilibrium.
Unfortunately, as Simon (1982) pointed out, real
economic entities have limited time and limited powers of
deliberation. He proposed the study of {\em bounded rationality},
investigating ``$\ldots$ the shape of a system in which effectiveness
in computation is one of the most important weapons of survival.''
Simon's work focussed mainly on {\em satisficing} designs, which
deliberate until reaching some solution satisfying a preset
``aspiration level.'' The results have descriptive value for modelling
various actual entities and policies, but no general prescriptive
framework for bounded rationality was developed. Although it proved
possible to calculate optimal aspiration levels for certain problems,
no structural variation was allowed in the agent design.

In the theory of games, bounds on the complexity of players have
become a topic of intense interest. For example, it is a troubling
fact that defection is the only equilibrium strategy for unbounded
agents playing a fixed number of rounds of the Prisoners' Dilemma
game. Neyman's theorem (Neyman, 1985), recently proved by
Papadimitriou and Yannakakis (1994), shows that an essentially
cooperative equilibrium exists if each agent is a finite automaton
with a number of states that is less than exponential in the number of
rounds. This is essentially a bounded optimality result, where the
bound is on space rather than on speed of computation.  This type of
result is made possible by a shift from the problem of selecting {\em
  actions} to the problem of selecting {\em programs}.



I.~J.~Good (1971) distinguished between perfect or ``type~I''
rationality, and metalevel or ``type~II'' rationality. He defines this
as ``the maximization of expected utility {\em taking into account
  deliberation costs}.''  Simon (1976) also says: ``The global
optimization problem is to find the least-cost or best-return
decision, {\em net} of computational costs.''  Although type II
rationality seems to be a step in the right direction, it is not
entirely clear whether it can be made precise in a way that respects
the desirable intuition that computation is important.  We will try
one interpretation, although there may be others.\footnote{For
  example, it is conceivable that Good and Simon really intended to
  refer to finding an agent design that minimizes deliberation costs
  in general. All their discussions, however, seem to be couched in
  terms of finding the right deliberation for each decision. Thus,
  type II or metalevel rationality coincides with bounded optimality
  if the bounded optimal agent is being designed for a {\it single}
  decision in a {\it single} situation.} The key issue is the space
over which the ``maximization'' or ``optimization'' occurs. Both Good
and Simon seem to be referring to the space of possible deliberations
associated with a {\em particular decision}. Conceptually, there is an
``object-level machine'' that executes a sequence of computations
under the control of a ``meta-level machine.'' The outcome of the
sequence is the selection of an external action. An agent exhibits
type II rationality if at the end of its deliberation and subsequent
action, its utility is maximized compared to all possible
deliberate/act pairs in which it could have engaged. For example, Good
discusses one possible application of type II rationality in chess
programs.  In this case, the object-level steps are node expansions in
the game tree, followed by backing up of leaf node evaluations to show
the best move. For simplicity we will assume a per-move time limit.
Then a type II rational agent will execute whichever sequence of node
expansions chooses the best move, of all those that finish before the
time limit.\footnote{One would imagine that in most cases the move
  selected will be the same move selected by a Type I agent, but this
  is in a sense ``accidental'' because further deliberation might
  cause the program to abandon it.} Unfortunately, the computations
required in the ``metalevel machine'' to select the object-level
deliberation may be extremely expensive. Good actually proposes a
fairly simple (and nearly practical) metalevel decision procedure for
chess, but it is far from optimal. It is hard to see how a type II
rational agent could justify executing a suboptimal object-level
computation sequence if we limit the scope of the optimization problem
to a single decision. The difficulty can only be resolved by thinking
about the design of the agent program, which generates an unbounded
set of possible deliberations in response to an unbounded set of
circumstances that may arise during the life of the agent.

Philosophy has also seen a gradual evolution in the definition of
rationality. There has been a shift from consideration of
{\em act utilitarianism} --- the 
rationality of individual acts --- to {\em rule utilitarianism}, or
the rationality of general policies for acting.
This shift has been caused by difficulties
with
individual versus societal rationality, rather than any consideration
of the difficulty of computing rational acts. Some consideration has
been given more recently to the tractability of general moral policies,
with a view to making them 
understandable and usable by persons of average intelligence (Brandt, 1953).
Cherniak (1986) has suggested a
definition of ``minimal rationality'', specifying lower bounds on the
reasoning powers of any rational agent, instead of upper bounds. A
philosophical proposal generally consistent with the notion of bounded
optimality can be found in Dennett's ``Moral First Aid
Manual'' (1986).
Dennett explicitly discusses the
idea of reaching equilibrium within the space of
decision procedures. He uses as an example the PhD
admissions procedure of a philosophy department. He concludes, as do
we, that the best procedure may be neither elegant nor
illuminating. The existence of such a procedure, and the process
of reaching it, are the main points of interest.

Many researchers in AI, some of whose work is discussed below, have
worked on the problem of designing agents with limited computational
resources. The 1989 AAAI Symposium on AI and Limited
Rationality (Fehling \& Russell, 1989) contains an interesting variety of work on
the topic. Much of this work is concerned with metalevel rationality.

Metareasoning --- reasoning about reasoning --- is an important
technique in this area, since it enables an agent to control its
deliberations according to their costs and benefits.  Combined with
the idea of {\em anytime} (Dean \& Boddy, 1988) or {\em flexible}
algorithms (Horvitz, 1987), that return better results as time
goes by, a simple form of metareasoning allows an agent to behave well
in a real-time environment. A simple example is provided by
iterative-deepening algorithms used in game-playing. Breese and
Fehling (1990) apply similar ideas to controlling
multiple decision procedures. Russell and
Wefald (1989) give a general method for
precompiling certain aspects of metareasoning so that a system can
efficiently estimate the effects of individual computations on its
intentions, giving fine-grained control of reasoning. These techniques
can all be seen as approximating metalevel rationality; they provide
useful insights into the general problem of control of reasoning, but
there is no reason to suppose that the approximations used are optimal
in any sense.

The intuitive notion of bounded optimality seems to have become 
current in the AI community in the mid-1980's.
Horvitz (1987) uses the term {\em bounded optimality} to
refer to ``the optimization of computational utility given a set of
assumptions about expected problems and constraints in reasoning
resources.''  Russell and Wefald (1991) say that
an agent exhibits bounded optimality for a given task environment ``if
its program is a solution to the constrained optimization problem
presented by its architecture.''  Recent work by
Etzioni (1989) and Russell and
Zilberstein (1991) can be seen as
optimizing over a well-defined set of agent designs, thereby making
the notion of bounded optimality more precise.  In the next section,
we build a suitable set of general definitions from the ground up, so
that we can begin to demonstrate examples of provably bounded optimal
agents.

\section{Agents, Architectures and Programs}\label{agents-section}

Intuitively, an {\em agent} is just a physical entity that we wish to
view in terms of its {\em perceptions} and {\em actions}.  What counts
in the first instance is what it does, not necessarily what it thinks,
or even whether it thinks at all. This initial refusal to consider
further constraints on the internal workings of the agent (such as
that it should reason logically, for example) helps in three ways:
first, it allows us to view such ``cognitive faculties'' as planning
and reasoning as occurring {\em in the service of\/} finding the right
thing to do; second, it makes room for those among us (Agre \&
Chapman, 1987; Brooks, 1986) who take the position that systems can do
the right thing without such cognitive faculties; third, it allows
more freedom to consider various specifications, boundaries and
interconnections of subsystems.

We begin by defining agents and environments in terms of the actions
and percepts that they exchange, and the sequence of states they go
through. The agent is described by an {\em agent function} from
percept sequences to actions. This treatment is fairly standard
(see, e.g., Genesereth \& Nilsson, 1987).
We then go ``inside'' the agent to look at the {\em agent program} that
generates its actions, and define the ``implementation'' relationship
between a program and the corresponding agent function. We 
consider performance measures on agents, and the problem of designing
agents to optimize the performance measure. 

\subsection{Specifying agents and environments}

An agent can be described abstractly as a mapping (the {\em agent
  function}) from percept sequences to actions.  Let $\O$ be the set
of percepts that the agent can receive at any instant, and $\A$ be the
set of possible actions the agent can carry out in the external world.
Since we are interested in the behaviour of the agent over time, we
introduce a set of time points or instants, $\T$. The set $\T$ is
totally ordered by the $<$ relation with a unique least element.
Without loss of generality, we let $\T$ be the set of non-negative
integers.

The percept history of an agent is
a sequence of percepts indexed by time. 
We define the set of percept histories
to be $\PT = \{\pT : \T \to \O\}$.  The prefix of a history
$\pT \in \PT$ till time $t$ is denoted $\pt$ and is the projection
of $\pT$ on $[0..t]$. We can define the set of percept history prefixes as
$\Pt = \{\pt \mid t \in \T, \pT \in \PT\}$.
Similarly, we define the set of action histories
$\AT = \{ \aT : \T \to \A\}$.
The set of action history prefixes is $\At$, defined as the set of
projections $\at$ of histories $\aT \in \AT$.

\begin{definition}\label{agent}
Agent function: a mapping
\[f: \Pt \rightarrow \A\]
where
\[\aT(t) = f(\pt)\]
\end{definition}
Note that the agent function is an entirely abstract entity, unlike the agent
program that implements it. Note also that the ``output'' of the agent
function for a given percept sequence may be a null action, for
example if the agent is still thinking about what to do. The agent
function specifies what the agent does at each time step. This is
crucial to the distinction between perfect rationality and calculative
rationality.


Agents live in environments.  The states of an environment $E$ are
drawn from a set $\X$.  The set of possible state trajectories is
defined as $\XT = \{\xT : \T \to \X \}$.  The agent does not
necessarily have full access to the current state $\xT(t)$,
but the percept received by the agent does depend on the current
state through the {\em perceptual filtering function}
$f_p$.  The effects of the agent's actions are represented by the 
environment's {\em transition function} $f_e$, which specifies the
next state given the current state and the agent's action.
An environment is
therefore defined as follows:
\begin{definition}{Environment} $E$: a set of states $\X$ with a
  distinguished initial state $X_0$, 
  a transition function $f_e$ and a perceptual filter
  function $f_p$ such that
\begin{eqnarray*}
\xT(0) & = & X_0 \\
\xT(t+1) &  = & f_e(\aT(t),\xT(t)) \\
\pT(t) & = & f_p(\xT(t)) 
\end{eqnarray*}
\end{definition}
%% a brief discussion of why f_e does not take \at and \xt as args.
The state history $\xT$ is thus determined by the environment and the
agent function. We use the notation $\effects(f,E)$ to denote the state
history generated by an agent function $f$ operating in an environment $E$.
We will also use the notation $[E,\at]$ to denote the state history
generated by applying the action sequence $\at$ starting in
the initial state of environment $E$.




Notice that the environment is discrete and deterministic in this
formulation.
We can extend the definitions to cover non-deterministic and
continuous environments, but at the cost of additional complexity in
the exposition. None of our results depend in a significant way on
discreteness or determinism.


\subsection{Specifying agent implementations}

We will consider a physical agent as consisting of an architecture and
a program. The architecture is responsible for interfacing between the
program and the environment, and for running the program itself. With
each architecture $M$, we associate a finite programming language
${\cal L}_M$, which is just the set of all programs runnable by the
architecture. An {\em agent program} is a program $l \in {\cal L}_M$
that takes a percept as input and has an internal state drawn from a
set $\I$ with initial state $i_0$. (The initial internal state depends
on the program $l$, but we will usually suppress this argument.)
The set of possible internal state histories is $\IT =
\{\iT : \T \to \I \}$.  The prefix of an internal state
history $\iT \in \IT$ till time $t$ is denoted $\jt$ and is the
projection of $\iT$ on $[0..t]$.  
\begin{definition}\label{architecture}
An architecture $M$ is a fixed interpreter for an agent program
that runs the program for a single time step, updating its internal
state and generating an action:
\[ M : {\cal L}_M \times \I \times \O \to \I \times \A \]
where
\[\langle \iT(t+1),\aT(t)\rangle =  M(l,\iT(t),\pT(t))\]
\end{definition}
Thus, the architecture generates a stream of actions according to the
dictates of the program. Because of the physical properties of the
architecture, running the program for a single time step results in
the execution of only a finite number of instructions. The program may
often fail to reach a ``decision'' in that time step, and as a result
the action produced by the architecture may be null (or the same as
the previous action, depending on the program design).


\subsection{Relating agent specifications and implementations}

We can now relate agent programs to the corresponding agent functions.
We will say that an agent program $l$ running on a machine $M$ {\it
implements} the agent function $Agent(l,M)$. The agent function
is constructed in the following definition by specifying the action sequences
produced by $l$ running on $M$ for all possible percept
sequences. Note the importance of the ``Markovian'' construction using
the internal state of the agent to ensure that actions can only be
based on the past, not the future.

\begin{definition}\label{correspondence}
A program $l$ running on $M$ 
implements the agent function $f = Agent(l,M)$, defined as follows. 
For any environment $E=(\X,f_e,f_p)$,
$f(\pt) =  \aT(t)$ where
\begin{eqnarray*}
\langle \iT(t+1),\aT(t)\rangle & = & M(l,\iT(t),\pT(t)) \\
\pT(t) & = & f_p(\xT(t)) \\
\xT(t+1) &  = & f_e(\aT(t),\xT(t)) \\
\xT(0) & = & X_0 \\
\iT(0) & = & i_0
\end{eqnarray*}
\end{definition}


Although every program $l$ induces a
corresponding agent function $Agent(l,M)$, the action that 
follows a given
percept is not necessarily the agent's ``response'' to that percept;
because of the delay incurred by deliberation, it may only reflect
percepts occurring much earlier in the sequence.
Furthermore, it is not possible to map every agent function to
an implementation $l \in {\cal L}_M$.  We can define a subset
of the set of agent
functions $f$ that are implementable on a given architecture $M$ and
language ${\cal L}_M$:
\[ Feasible(M) = \{f \mid \exists l \in {\cal L}_M, \; f =
Agent(l,M)\}\]
Feasibility is related to, but clearly distinct from, the
notion of computability. Computability refers to the existence of a
program that {\em eventually} returns the output specified by a
function, whereas feasibility refers to the production of the output
at the appropriate point in time. The set of feasible agent functions
is therefore much smaller than the set of computable agent functions. 



\subsection{Performance measures for agents}

To evaluate an agent's performance in the world, we define a
real-valued utility function $U$ on state histories:
\[ U: \XT \to \Re \] 
The utility function should be seen as external to the agent and its
environment. It defines the problem to be solved by the designer of
the agent. {\it Some} agent designs may incorporate an explicit
representation of the utility function, but this is by no means
required. We will use the term {\em task environment} to denote the
combination of an environment and a utility function.


Recall that the agent's actions drive the environment $E$
through a particular sequence of states in accordance with the
function $\effects(f,E)$.  We can define the value of an agent
function $f$ in the environment $E$ as the utility of the state
history it generates:
\[ V(f,E) = U(\effects(f,E)) \]
If the designer has a set $\E$ of environments with a probability
distribution $p$ over them, instead of a single environment $E$, then
the value of the agent in $\E$ is defined as the expected value
over the elements of $\E$. By a slight abuse of notation,
\[ V(f,\E) = \sum_{E \in \smallE}^{} p(E) V(f,E) \]


We can assign a value $V(l,M,E)$ to a program $l$ executed by the
architecture $M$ in the environment $E$ simply by looking at the
effect of the agent function implemented by the program:
\[ V(l,M,E)  =  V(Agent(l,M),E) = U(\effects(Agent(l,M),E)) \]
As above, we can extend this to a set of possible environments as follows:
\[ V(l,M,\E) = \sum_{E \in \smallE}^{} p(E) V(l,M,E) \]

\subsection{Perfect rationality and bounded optimality}

As discussed in Section~\ref{history-section}, a perfectly rational
agent selects the action that maximizes its expected utility, given
the percepts so far. In our framework, this amounts to an agent function
that 
maximizes $V(f,\E)$ over all possible agent functions.
\begin{definition} A perfectly rational agent for a set $\E$ of
environments has an agent function $\fopt$ such that
\[\fopt = \argmax_f(V(f,\E))\]
\end{definition}

This definition is a persuasive specification of an optimal agent
function for a given set of environments, and underlies several
recent projects in intelligent agent design (Dean \& Wellman,1991;
Doyle, 1988; Hansson \& Mayer, 1989). A direct implementation of this
specification, which ignores the delay incurred by deliberation, does
not yield a reasonable solution to our problem -- the calculation of
expected utilities takes time for any real agent.  In terms of our
simple formal description of agents introduced above, it is easy to
see where the difficulty has arisen.  In designing the agent program,
logicists and decision theorists have concentrated on specifying an
optimal agent function $\fopt$ in order to guarantee the selection of
the best action history. The function $\fopt$ is independent of the
architecture $M$.  Unfortunately, no real program in ${\cal L}_M$
implements this function in a non-trivial environment, because optimal
actions cannot usually be computed before the next percept arrives.
That is, quite frequently, $\fopt \not\in Feasible(M)$.


Suppose the environment consists of games of chess under tournament
rules against some population of human grandmasters, and suppose $M$
is some standard personal computer. Then $\fopt$ describes an agent
that always plays in such a way as to maximize its total expected
points against the opposition, where the maximization is over the {\em
moves} it makes. We claim that no possible program can play this way.
It is quite possible, using depth-first alpha-beta search to
termination, to execute the program that chooses (say) the optimal minimax
move in each situation, but the agent function induced by this program
is not the same as $\fopt$. In particular, it ignores such percepts as
the dropping of its flag indicating a loss on time.



The trouble with the perfect rationality definition arose because of
unconstrained optimization over the space of $f$'s in the
determination of $\fopt$, without regard to feasibility.
(Similarly, metalevel rationality assumes unconstrained optimization
over the space of deliberations.)
To escape this quandary, we propose a machine-dependent standard of
rationality, in which we maximize $V$ over the implementable set of
agent functions $Feasible(M)$.  That is, we impose optimality
constraints on {\em programs} rather than on {\em agent functions}
or {\em deliberations}.



\begin{definition}
A bounded-optimal agent with architecture $M$ 
for a set $\E$ of
environments has an agent program $\lopt$ such that
\[\lopt = \argmax_{l\in {\cal L}_M} V(l,M,\E)\]
\end{definition}

%\begin{figure}[ht]
%\epsfxsize=4.5in
%\centerline{
%\epsffile{bofig.ps}}
%\caption{An illustration of the difference between bounded optimal
% programs and optimal agent
%  functions in an episodic, real-time environment.}
%\label{mail-sorter-figure}
%\end{figure}

We can see immediately that this specification avoids the most obvious
problems with Type I and Type II rationality. Consider
our chess example, and suppose the computer has a total
program memory of 8 megabytes. Then there are $2^{2^{26}}$ possible
programs that can be represented in the machine, of which a much
smaller number play legal chess. Under tournament conditions, one or
more of these programs will have the best expected performance.
Each is a suitable candidate for $\lopt$. Thus bounded optimality is,
by definition, a feasible specification; moreover, a program that
achieves it is highly desirable.
We are not yet ready to announce the identity
of $\lopt$ for chess on an eight-megabyte PC, so we will begin with a
more restricted problem.



\section{Provably Bounded-Optimal Agents} \label{bo-section} 

In order to construct a provably bounded optimal agent, we must
carry out the following steps:
\begin{itemize}
\item Specify the properties of the environment in which actions will
  be taken, and the utility function on the behaviours.
\item Specify  a class of machines on
which programs are to be run. \item Propose a construction method.
\item Prove that the construction method succeeds in building bounded
  optimal agents.
\end{itemize}
The methodology is similar to the formal analysis used in the field of
optimal control, which studies the design of {\em
controllers} (agents) for {\em plants} (environments). In optimal
control theory, a controller is viewed as an essentially instantaneous
implementation of an optimal agent function. In contrast, we
focus on the computation time required by the agent, and the relation
between computation time and the dynamics of the environment.

\subsection{Episodic, real-time task environments}

In this section, we will consider a restricted
class of task environments which we call {\em episodic} environments.  In
an episodic task environment, the state history generated by the actions of
the agent can be considered as divided into a series of {\em
episodes}, each of which is terminated by an action. 
Let 
$\Abot \subseteq \A$ be a distinguished set of actions
that terminate an episode. 
The utility of
the complete history is given by the sum of the utilities of each
episode, which is determined in turn by the state sequence. After each
$A \in \Abot$, the environment
``resets'' to a state chosen at random from a stationary probability
distribution $P_{init}$. In order to include the effects of the choice
of $A$ in the utility of the episode, we notionally
divide the environment state into a ``configuration'' part and a
``value'' part, such that the configuration part determines the state
transitions while the value part determines the utility of a state
sequence. Actions in $\Abot$ reset the configuration part, while
their ``value'' is recorded in the value part.
These restrictions mean that
each episode can be treated as a separate decision problem,
and translate into the
following property: if agent program $l_1$ has higher expected utility
on individual episodes than agent $l_2$, it will have higher expected
utility in the corresponding episodic task environment.

A real-time task environment is one in which the utility of an action
depends on the time at which it is executed. Usually, this dependence
will be sufficiently strong to make calculative rationality an
unacceptably bad approximation to perfect rationality.


\begin{figure}[ht]
\epsfxsize=4.5in
\centerline{
\epsffile{mail-sorter.ps}}
\caption{An automated mail-sorting facility provides a simple example
of an episodic, real-time task environment.}
\label{mail-sorter-figure}
\end{figure}



An automated mail sorter\footnote{See (Sackinger et al. 1992; Boser et
  al. 1992) for details of an actual system. The application was
  suggested to us by Bernhard Boser after an early presentation of our
  work at the 1992 NEC Symposium.} provides an illustrative example of
an episodic task environment (see Figure~\ref{mail-sorter-figure}).
Such a machine scans handwritten or printed addresses (zipcodes) on
mail pieces and dispatches them to appropriate bins.  Each episode
starts with the arrival of a new mail piece and terminates with the
execution of the physical action recommended by the sorter: routing of
the piece to a specific bin.  The ``configuration part'' of the
environment corresponds to the letter feeder side, which provides a
new, randomly selected letter after the previous letter is sorted. The
``value part'' of the state corresponds to the state of the receiving
bins, which determines the utility of the process. The aim is to
maximize the accuracy of sorting while minimizing the reject
percentage and avoiding jams. A jam occurs if the current piece is not
routed to the appropriate bin, or rejected, before the arrival of the
next piece.

We now provide formal definitions for
three varieties of real-time task environments: fixed deadlines, fixed time
cost and stochastic deadlines.

\subsubsection{Fixed deadlines}

The simplest and most commonly studied kind of real-time task environment
contains a deadline at a known time. In most work on real-time
systems, such deadlines are described informally and systems are built
to meet the deadline. Here, we need a formal specification in order to
connect the description of the deadline to the properties of agents
running in deadline task environments. One might think that deadlines are
part of the environment description, but in fact they are mainly
realized as constraints on the utility function. One can see this by
considering the opposite of a deadline --- the ``starter's pistol.''
The two are distinguished by differing constraints on the utilities of
acting before or after a specific time.

\begin{definition}{Fixed deadline}: \label{fixed-deadline-def}
The task environment $\langle E, U \rangle$ has a fixed deadline at
time $t_d$ if the following conditions hold.
\begin{itemize}
\item Taking an action in $\Abot$ at any time before the deadline
results in the same utility:
\[
U([E,A_1^t]) = U([E,A_2^{(t_d-1)}\cdot A_1^{\smallT}(t)])
\]
where ``$\cdot$'' denotes sequence concatenation,
$t \leq t_d$, $A_1^{\smallT}(t) \in \Abot$,
and $A_1^{(t-1)}$ and $A_2^{(t_d-1)}$ contain no action in $\Abot$.
\item Actions taken after $t_d$ have no effect on utility:
\[
U([E,A_1^t]) \leq U([E,A_2^t]) \mbox{ if } 
U([E,A_1^{t_d}]) \leq U([E,A_2^{t_d}]) \mbox{ and } t\geq t_d
\]
\end{itemize}
\end{definition}



\subsubsection{Fixed time cost}

Task environments with approximately fixed time cost are also very common. Examples
include consultations with lawyers, keeping a taxi waiting, or
dithering over where to invest one's money. We can define a task
environment with fixed time cost $c$ by comparing the utilities of
actions taken at different times.

\begin{definition}{Fixed time cost}:
\label{fixed-cost-def}
The task environment $\langle E, U \rangle$ has a fixed time cost if,
for any action history prefixes $A_1^{t_1}$ and
$A_2^{t_2}$ satisfying
\[\begin{array}{l}
(1)\quad A_1^{\smallT}(t_1) \in \Abot \mbox{ and }
A_2^{\smallT}(t_2) = A_1^{\smallT}(t_1)\\
(2)\quad A_1^{(t_1-1)} \mbox{ and } A_2^{(t_2-1)} 
         \mbox{ contain no action in } \Abot
\end{array}\]
the utilities differ by the difference in time cost:
\[
U([E,A_2^{t_2}]) = U([E,A_1^{t_1}]) - c(t_2 - t_1)
\]
\end{definition}
Strictly speaking, there are no task environments with fixed time cost. 
Utility values have a finite range, so one cannot continue incurring
time costs indefinitely. For reasonably short times and reasonably
small costs, a linear utility penalty is a useful approximation.

\subsubsection{Stochastic deadlines}

While fixed-deadline and fixed-cost task environments occur frequently in the
design of real-time systems, uncertainty about the time-dependence of
the utility function is more common. It also turns out to be more
interesting, as we see below.

A stochastic deadline is represented by uncertainty concerning the
time of occurrence of a fixed deadline. In other words, the agent has
a probability distribution
$p_d$ for the deadline time $t_d$.
We assume that the deadline must come eventually, so that 
$\sum_{t \in \smallT} p_d(t) = 1$. We also define the cumulative
deadline distribution $P_d$. 


If the deadline does not occur at a known time, then we need to
distinguish between two cases:
\begin{itemize}
\item The agent receives a percept, called a {\em herald} (Dean \&
  Boddy, 1988), which announces an impending deadline.  We model this
using a distinguished percept $\od$:
\[\pT(t_d) = \od\]
If the agent responds immediately, then it ``meets the deadline.''
\item No such percept is available, in which case
the agent is walking
blindfolded towards the utility cliff. By deliberating further, the
agent risks missing the deadline but may improve its decision quality.
An example familiar to most readers is that of deciding whether to
publish a paper in its current form, or to embellish it further and
risk being ``scooped.''
We do not treat this case in the current paper.
\end{itemize}
Formally, the stochastic deadline case is similar to the fixed
deadline case, except that $t_d$ is
drawn from the distribution $p_d$. The utility of executing
an action history prefix $\at$ in $\E$
is the expectation of the utilities of that state history
prefix over the possible deadline times.

\begin{definition}\label{stochastic-deadline-def}{Stochastic
deadline}: 
A task environment class $\langle \E, U \rangle$ of fixed-deadline
task environments
has a stochastic deadline distributed according to $p_d$ if, for any
action history prefix $\at$,
\[ U([\E,\at]) = \sum_{t'\in\smallT} p_d(t')U([E_{t'},A^{t}]) \]
where $\langle E_{t'}, U \rangle$ is a task environment in
$\langle \E, U \rangle$ with a fixed deadline at $t'$.
\end{definition}

The mail sorter example is well described by a stochastic deadline.
The time between the arrival of mail pieces at the image processing
station is distributed according to a density function $p_d$, which
will usually be Poisson.



\subsection{Agent programs and agent architecture} \label{prod-systems}

We consider simple agent programs for episodic task environments,
constructed from elements of a set $\R = \{r_1, \ldots, r_n\}$ of
decision procedures or rules.  Each decision procedure recommends (but
does not execute) an action $A_i \in \Abot$, and an agent program is a
fixed sequence of decision procedures.  For our purposes, a decision
procedure is a black box with two parameters:
\begin{itemize}
\item a run time $t_i \geq 0$, which is an integer that
  represents the time taken by the procedure to compute an action.
\item a quality $q_i \geq 0$, which is a real number.
  This gives the expected reward resulting
>from executing its action $A_i$ at the start of an episode:
\begin{equation}
q_i = U([E,A_i])
\label{q-def}
\end{equation}

\end{itemize}
Let
$M_{{\cal J}}$ denote an agent architecture that executes decision 
procedures in the language ${\cal J}$.  Let $t_M$ denote the 
maximum runtime of the decision procedures that can be accommodated in $M$.
For example, if the runtime of a feedforward neural network
is proportional to its size, then $t_M$ will be the runtime of the 
largest neural network that fits in $M$.


The architecture $M$ executes an agent program $s = s_1 \ldots s_m$ by
running each decision procedure in turn, providing the same input to
each as obtained from the initial percept.  When a deadline arrives
(at a fixed time $t_d$, or heralded by the percept $\od$), or when the
entire sequence has been completed, the agent selects the action
recommended by the highest-quality procedure it has executed:
\begin{eqnarray}\label{arch}
M(s,\iT(t_d),\pT(t_d)) & = & \langle i_0,\action(\iT(t_d))\rangle \nonumber\\
M(s,\iT(t_s),\pT(t_s)) & = & \langle i_0,\action(\iT(t_s))\rangle 
\mbox{ where } t_s = {\textstyle\sum_{s_i \in s} t_i} \\
M(s,\iT(t),\od) & = & \langle i_0,\action(\iT(t))\rangle \nonumber
\end{eqnarray}
where $M$ updates the agent's internal state history $\iT(t)$ such
that $\action(\iT(t))$ is the action recommended by a completed
decision procedure with the highest quality. When this action is
executed, the internal state of the agent is re-initialized to $i_0$.
This agent design works in all three of the task environment categories
described above.

Next we derive the value $V(s,M,E)$ of an agent program $s$ in
environment $E$ running on $M$ for the three real-time regimes and
show how to construct bounded optimal agents for these task
environments.


\subsection{Bounded optimality with fixed deadlines}

{From} Equation~\ref{arch}, we know that the agent
picks the action in $\Abot$ recommended by the decision procedure $r$
with the highest quality that is executed before the deadline $t_d$
arrives.  Let $s_1 \ldots s_j$ be the longest prefix of the program
$s$ such that $\sum_{i=1}^j t_i \leq t_d$. 
{From} Definition~\ref{fixed-deadline-def} and Equation~\ref{q-def},
it follows that 
\begin{equation}\label{fixed-deadline-value}  
V(s,M,E) = Q_j
\end{equation}
where $Q_i = \max\{q_1,\ldots, q_i\}$.
Given this expression for the value of the agent program, we
can easily show the following:
\begin{theorem}\label{opt-fixed-deadline}
Let $r* = \arg\max_{r_i{\,\in\,}\smallR,t_i\leq t_d} q_i$.
The singleton sequence $r*$ is a bounded optimal program
for $M$ in an episodic task environment with a known deadline $t_d$.
\end{theorem}
That is, the best program is the single decision procedure of maximum
quality whose runtime is less than the deadline. 


\subsection{Bounded optimality with fixed time cost}

{From} Equation~\ref{arch}, we know that the agent picks the action in
$\Abot$ recommended by the best decision procedure in the sequence,
since $M$ runs the entire sequence $s = s_1 \ldots s_m$ when there is
no deadline.  {From} Definition~\ref{fixed-cost-def} and
Equation~\ref{q-def}, we have
\begin{equation}\label{fixed-cost-value}  
V(s,M,E) = Q_m - c\sum_{i=1}^m t_i
\end{equation}
Given this expression for the value of the agent program, we
can easily show the following:
\begin{theorem}\label{opt-fixed-cost}
Let $r* = \arg\max_{r_i{\,\in\,}\smallR}
q_i - ct_i$.
The singleton sequence $r*$ is a bounded optimal program
for $M$ in an episodic task environment with a fixed time cost $c$.
\end{theorem}
That is, the optimal program is the single decision procedure whose
quality, net of time cost, is highest.


\subsection{Bounded optimality with stochastic deadlines}
\label{execution-time-distribution-section}

With a stochastic deadline distributed according to $p_d$, the value
of an agent program $s=s_1 \ldots s_m$ is an expectation. From
Definition~\ref{stochastic-deadline-def}, we can calculate this as
$\sum_{t\in\smallT} p_d(t) V(s,M,E_t)$, where $\langle E_t,U\rangle$
is a task environment with
a fixed deadline at $t$.  After substituting for $V(s,M,E_t)$ from
Equation~\ref{fixed-deadline-value}, this expression simplifies
to a summation, over the procedures in the sequence, of the probability
of interruption after the $i^{th}$ procedure in the sequence
multiplied by the
quality of the best completed decision procedure:
\begin{equation}
V(s) \equiv 
V(s,M,\E) = \sum_{i=1}^{m} [P_d(\textstyle{\sum_{j=1}^{i+1} t_{j}}) -
P_d(\textstyle{\sum_{j=1}^{i} t_{j}})] Q_i
\label{stochastic-value-def}
\end{equation}
where $P_d(t) = \int_{-\infty}^t p_d(t')dt'$ and $P_d(t) = 1$ for $t
\geq \sum_{i=1}^{m}t_i$.




A simple example serves to illustrate the value function. Consider
$\R
= \{ r_1, r_2, r_3\}$. The rule $r_1$ has a quality of 0.2 and needs 2
seconds to run: we will represent this by $r_1 = (0.2,2)$. The other
rules are $r_2 = (0.5,5),\ r_3 = (0.7,7)$. The deadline distribution
function $p_d$ is a uniform distribution over 0 to 10
seconds. The value of the sequence $r_1 r_2 r_3$ is 
\[ V(r_1 r_2 r_3) = [.7 - .2] .2 + [1 - .7] .5 + [1 - 1] .7 = .25 \]

A geometric intuition is given by the notion of a {\em performance
profile}, as shown in Figure~\ref{profile-fig}.  
\begin{definition}\label{perf-profile}{Performance profile}: 
For a sequence $s$, the
  performance profile $Q_s(t)$ gives the quality of the action returned
  if the agent is interrupted at $t$: \[Q_s(t) = max \{q_i: \sum_{j=1}^i
  t_j \leq t\} \] \end{definition}


For a uniform deadline
density function, the value of a sequence is proportional to the area
under the performance profile up to the last possible interrupt time.
Note that the height of the
profile during the interval of length $t_i$ while rule $i$ is running
is the quality of the best of the {\em previous} rules.

\begin{figure}
\epsfxsize=0.8\textwidth
\centerline{\epsffile{profile-fig.ps}}
\caption{Performance profile for $r_1 r_2 r_3$, with $p_d$ superimposed.}
\label{profile-fig}
\end{figure}


{From}
Definition~\ref{perf-profile}, we have the following obvious property:
\begin{lemma}
The performance profile of any sequence is monotonically nondecreasing.
\label{nondecreasing-profile}
\end{lemma}
It is also the case that a sequence with higher quality
decisions at all times is a better sequence:
\begin{lemma}
If $\forall t \ Q_{s_1}(t) \geq Q_{s_2}(t)$, then $V(s_1) \geq V(s_2)$.
\label{dominating-profile}
\end{lemma}
In this case we say that $Q_{s_1}$ {\em dominates} $Q_{s_2}$.


We can use the idea of performance profiles to establish some useful
properties of optimal sequences.

\newsavebox{\sbqordering}
\sbox{\sbqordering}{\parbox{\textwidth}{%
\begin{lemma}\label{qordering}
There exists an optimal sequence that is sorted in increasing order of $q$'s.
\end{lemma}%
}}

\noindent\usebox{\sbqordering}

Without 
Lemma~\ref{qordering}, there are 
$\sum_{i=1}^{n} i!$ 
possible sequences to consider. The ordering constraint eliminates
all but $2^n$ sequences.
It also means that in proofs of properties of sequences, we now need
consider only ordered sequences. In addition, we can replace $Q_i$ in
Equation~\ref{stochastic-value-def}
by $q_i$.

The following lemma establishes that a sequence can always be improved
by the addition of a better rule at the end:

\newsavebox{\sbaddbetter}
\sbox{\sbaddbetter}{\parbox{\textwidth}{%
\begin{lemma}\label{addbetter}
  For every sequence $s = s_1 \ldots s_m$ sorted in increasing
  order of quality, and single step z with $q_z \geq q_{s_m}$, $V(sz)
\geq V(s)$.  
\end{lemma} %
}}

\noindent\usebox{\sbaddbetter}

\begin{corollary} \label{last-element}
There exists an optimal sequence ending with the
highest-quality rule in $\R$.
\end{corollary}


The following lemma reflects the obvious intuition that if one can
get a better result in less time, there's no point spending more time
to get a worse result: 

\newsavebox{\sbtordering}
\sbox{\sbtordering}{\parbox{\textwidth}{%
\begin{lemma}\label{t-ordering-lemma} 
There exists an optimal
sequence whose rules are in nondecreasing order of $t_i$.
\end{lemma} %
}}

\noindent\usebox{\sbtordering}

We now apply these preparatory results to derive algorithms that
construct bounded optimal programs for various deadline distributions.


\subsubsection{General distributions} 

For a general deadline distribution, the {\em dynamic programming}
method can be used to obtain an optimal sequence of decision rules in
pseudo-polynomial time.  We construct an optimal sequence by using the
definition of $V(s,M,E)$ in Equation~\ref{stochastic-value-def}.
Optimal sequences generated by the methods are ordered by $q_i$, in
accordance with Lemma~\ref{qordering}.
 
We
construct the table $S(i,t)$, where each entry in the table is the
highest value of any sequence that ends with rule $r_i$ at time $t$. We
assume the rule indices are arranged in increasing order of quality,
and $t$ ranges from the start time 0 to the end time $L =
\textstyle\sum_{r_i\in \R} t_i$. The update rule is:
\[ 
  S(i,t) = max_{k \in [0\ldots i-1]} [S(k,t-t_i) + (q_i - q_k)[1 - P_d(t)]] 
\]
with boundary condition
\[ S(i,0) = 0 \mbox{ for each rule $i$ and } S(0,t) = 0 \mbox{ for
  each time t}\]
{From} Corollary~\ref{last-element}, we can read off the best sequence
>from the highest value in row $n$ of the matrix $S$. %%[[boundary conditions]]
\begin{theorem}
The DP algorithm computes an optimal sequence in
time $O(n^2L)$ where $n$ is the number of decision procedures in $\R$. 
\end{theorem}
The dependence on $L$ in the time complexity of the DP algorithm
means that the algorithm is not polynomial in the input size. Using
standard rounding and scaling methods, however, a fully polynomial
approximation scheme can be constructed. Although we do not have a
hardness proof for the problem, John Binder (1994) has shown that
if the deadline distribution is used as a
constant-time oracle for finding values of $P(t)$, any algorithm will
require an exponential number of calls to the oracle in the worst case.

\subsubsection{Long uniform distributions}

If the deadline is uniformly distributed over a time interval greater
than the sum of the running times of the rules, we will call the
distribution a {\em long uniform} distribution.  Consider the rule
sequence $s = s_1 \ldots s_m$ drawn from the rule set $\R$.  With a
long uniform distribution, the probability that the deadline arrives during
rule $s_i$ of the sequence $s$ is independent of the time at which
$s_i$ starts.  This permits a simpler form of
Equation~\ref{stochastic-value-def}:
\begin{equation}\label{simplified}
V(s,M,\E) = \textstyle{\sum _{i=1}
^{m-1} P_d(t_{i+1}) q_i}  + q_m(1 - \textstyle{\sum _{i=1} ^{m} P_d(t_i)}) 
\end{equation}

To derive
an optimal sequence under a long uniform distribution, we obtain a
recursive specification of the value of a sequence $as$ with $a \in \R$
and $s = s_1 \ldots s_m$ being some sequence in $\R$. 
\begin{equation}
 V(as,M,\E) = V(s,M,\E) + q_{a}P_d(t_1) - q_{m}P_d(t_{a})   \label{v-rtol}
\end{equation} 
This
allows us to define a dynamic programming scheme for calculating an
optimal sequence using a state function $S(i,j)$ denoting the highest
value of a rule sequence that starts with rule $i$ and ends in rule
$j$. From Lemma~\ref{qordering} and Equation~\ref{v-rtol}, the update rule
is:
\begin{eqnarray}\label{updates}
S(i,j) & = & max_{i < k \leq j} [ S(k,j) + P_d(t_k) q_i - P_d(t_i) q_j ]
\end{eqnarray}
with boundary condition
\begin{equation}\label{boundary}
S(i,i) = (1 - P_d(t_i)) q_i 
\end{equation}
{From} Corollary~\ref{last-element}, we know that an optimal sequence
for the long uniform distribution ends in $r_n$, the rule with the
highest quality in $\R$. Thus, we only need to examine $S(i,n), 1 \leq
i \leq n$. Each entry requires $O(n)$ computation, and there are $n$
entries to compute. Thus, the optimal sequence for the long uniform
case can be calculated in $O(n^2)$.

\begin{theorem}
  An optimal sequence of decision procedures for a long uniform
deadline distribution can be determined in $O(n^{2})$ time where $n$
is the number of decision procedures in $\R$.
\end{theorem}

\subsubsection{Short uniform distributions}
When $\sum_{i=1}^{n} P_d(t_i) > 1$, for a uniform deadline distribution
$P_d$, we call it {\em short}. This means that some sequences are
longer than the last possible deadline time, and therefore some rules
in those sequences have no possibility of executing before the
deadline. For such sequences, 
we
cannot use Equation~\ref{v-rtol} to calculate $V(s)$.
However, any such sequence can be truncated by removing all rules
that would complete execution after the last possible deadline.
The value of the sequence is unaffected by truncation, and for
truncated sequences the use of
Equation~\ref{v-rtol} is justified.  Furthermore, there is an optimal
sequence that is a truncated sequence.

Since the update rule~\ref{updates} correctly computes $S(i,j)$ for
truncated sequences, we can use it with short uniform distributions
provided we add a check to ensure that the sequences considered are
truncated. Unlike the long uniform case, however, the identity of the
last rule in an optimal sequence is unknown, so we need to compute all
$n^2$ entries in the $S(i,j)$ table.  Each entry computation takes
$O(n)$ time, thus the time to compute an optimal sequence is $O(n^3)$.


\begin{theorem}
  An optimal sequence of decision procedures for a short uniform
deadline distribution can be determined in $O(n^{3})$ time where $n$
is the number of decision procedures in $R$.
\end{theorem}



\subsubsection{Exponential distributions}
For an exponential distribution, $P_d(t) = 1 - e^{-\beta t}$.
Exponential distributions allow an optimal sequence to be computed in
polynomial time.
Let $p_i$ stand for the probability that rule $i$ is interrupted,
assuming it starts at $0$. Then
$ p_i = P_d(t_i) = 1 - e^{-\beta t_i}. $
For the exponential
distribution, $V(s,M,\E)$ simplifies out as:
\[ 
V(s,M,\E) = \sum_{i=1}^{m-1} \left[ \Pi_{j=1}^{i} (1 - p_j)\right]p_{i+1}q_i +
\left[ \Pi_{j=1}^{m} (1 - p_j)\right]q_m 
\]
This yields a simple recursive specification of the value
$V(as,M,\E)$ of a sequence that begins with the rule $a$:
\[ V(as,M,\E) = (1 - p_a)p_1 q_a + (1 - p_a) V(s,M,\E) \]
We will use the state function $S(i,j)$ which represents the highest
value of any rule sequence starting with $i$ and ending in $j$.
\[ S(i,j) = max_{i< k \leq j} \left[ (1 - p_i)p_k q_i + (1 - p_i) S(k,j)
\right] \]
with boundary  condition $S(i,i) = q_i(1 - p_i)$. For any given $j$,
$S(i,j)$ can be calculated in $O(n^2)$. 
{From} Corollary~\ref{last-element}, we know that there is an optimal
sequence whose last element is the highest-valued rule in $\R$.

\begin{theorem}

  An optimal sequence of decision procedures for an exponentially
  distributed stochastic deadline can be determined in $O(n^{2})$ time
  where $n$ is the number of decision procedures in $\R$.

\end{theorem}

\noindent The proof is similar to the long uniform distribution case. 

\subsection{Simulation results for a mail-sorter}

The preceding results provide a set of algorithms for optimizing the
construction of an agent program for a variety of general task environment
classes.  In this section, we illustrate these results and the
possible gains that can be realized in a specific task environment,
namely, a simulated mail-sorter.

First, let us be more precise about the utility function $U$ on 
episodes.
There are four possible outcomes; the utility of outcome $i$ is $u_i$.
\begin{enumerate}
\item The zipcode is successfully read and the letter is sent to the
correct bin for delivery.
\item The zipcode is misread and the letter goes to the wrong bin. 
\item The letter is sent to the reject bin.
\item The next letter arrives before the recognizer has finished, and
there is a jam. Since letter arrival is heralded, jams cannot occur
with the machine architecture given in Equation~\ref{arch}.
\end{enumerate}

\begin{figure}
\centerline{
\epsfxsize=0.48\textwidth
\epsffile{acc.ps}
\hfill
\epsfxsize=0.48\textwidth
\epsffile{poisson.ps}
}
\caption{(a) Accuracy profile ($1-e^{-\lambda x}$), for 
          $\lambda = 0.9$.
         (b) Poisson arrival distribution, for mean $\mu=9$ sec }
\label{nnsetup-figure}
\end{figure}

Without loss of generality, we set $u_1 = 1.0$ and $u_2 = 0.0$.  If
the probability of a rule recommending a correct destination bin is
$p_i$, then $q_i = p_iu_1 + (1-p_i)u_2 = p_i$.  We assume that $u_2
\leq u_3$, hence there is a threshold probability below which the
letter should be sent to the reject bin instead.  We will therefore
include in the rule set $\R$ a rule $r_{reject}$ that has zero runtime
and recommends rejection. The sequence construction algorithm will
then automatically exclude rules with quality lower than $q_{reject} =
u_3$. The overall utility for an episode is chosen to be a linear
combination of the quality of sorting ($q_i$), the probability of
rejection or the rejection rate (given by $P(t_1)$, where $t_1$ is the
runtime of the first non-reject rule executed), and the speed of
sorting (measured by the arrival time mean).

The agent program in (Boser et al. 1992) uses a single neural network
on a chip. We show that under a variety of conditions an optimized
sequence of networks can do significantly better than any single
network in terms of throughput or accuracy. We examine the
following experimental conditions:
\begin{itemize}
\item We assume that a network that executes in time $t$ has a
  recognition accuracy $p$ that depends on $t$. We consider
  $p=1-e^{-\lambda t}$. The particular choice of $\lambda$ is
  irrelevant because the scale chosen for $t$ is arbitrary.  We choose
  $\lambda = 0.9$, for convenience (Figure~\ref{nnsetup-figure}(a)).
  We include $r_{reject}$ with $q_{reject}=u_3$ and $t_{reject} = 0$.

\item We consider arrival time distributions that are Poisson with
varying means. Figure~\ref{nnsetup-figure}(b) shows three 
example distributions, for means 1, 5, and 9 seconds. 
\item We create optimized sequences from sets of 40 networks with
  execution times taken at equal intervals from $t=1$ to 40.
\item We compare 
\begin{itemize}
\item[(a)] BO sequence: a bounded optimal sequence;
\item[(b)] Best singleton: the best single rule;
\item[(c)] 50\% rule: the rule whose execution time is the mean of the distribution (i.e., it will complete in 50\% of cases);
\item[(d)] 90\% rule: the rule whose execution time guarantees that it
  will complete in 90\% of cases.
\end{itemize}
In the last three cases, we add $r_{reject}$ as an initial step;
the BO sequence will include it automatically.

\item We measure the utility per second as a function of
  the mean arrival rate (Figure~\ref{u-rate-figure}).  This shows that
  there is an optimal setting of the sorting machinery at 6 letters
  per minute (inter-arrival time = 10 seconds) for the bounded optimal
  program, given that we have fixed $\lambda$ at 0.9. 

\item Finally, we investigate the effect of the variance of the
  arrival time on the relative performance of the four program types.
  For this purpose, we use a uniform distribution centered around 20
  seconds but with different widths to vary the variance without
  affecting the mean (Figure~\ref{u-variance-figure}).

\end{itemize}


\begin{figure}
\leavevmode
\epsfxsize=0.8\textwidth
\centerline{\epsffile{bo.ps}}
\caption{Graph showing the achievable utility per second as a function of
the average time per letter, for the four program types.  $\lambda = 0.9$.}
\label{u-rate-figure}
\end{figure}

\begin{figure}
\leavevmode
\epsfxsize=0.8\textwidth
\centerline{
\epsffile{var.ps}
}
\caption{Graphs showing the utility gain per second as a function of
  the arrival time variance, for the four program types for the
  uniform distribution with a mean of 20 seconds. }
\label{u-variance-figure}
\end{figure}

We notice several interesting things about these results:
\begin{itemize}
\item The policy of choosing a rule with a 90\% probability of
  completion performs poorly for rapid arrival rates ($\mu \leq 3$),
  but catches up with the performance of the best single rule for
  slower arrival rates ($\mu > 4$). This is an artifact of the
  exponential accuracy profile for any $\lambda > 0.5$, where the
  difference in quality of the rules with run times greater than $6$
  seconds is quite small.

\item The policy of choosing a rule with a 50\% probability of
  completion fares as well as the best single rule for very high
  arrival rates ($\mu \leq 2$), but rapidly diverges from it
  thereafter, performing far worse for arrival time means
  greater than 5 seconds.

\item Both the best sequence and the best single rule give their
  best overall performance at an arrival rate of around 6 letters per minute.  The
  performance advantage of the optimal sequence over the best single
  rule is about 7\% at this arrival rate. It should be noted that
  this is a significant performance advantage that is obtainable with
  no extra computational resources.  For slower arrival rates 
  ($\mu\geq 7$), the difference between the performance of the best rule
  and the best sequence arises from the decreased rejection rate of the
  best sequence.  With the exponential accuracy profile ($\lambda \geq
  0.5$) the advantage of running a rule with a shorter completion time
  ahead of a longer rule is the ability to reduce the probability of
  rejecting a letter.  For high arrival rates (inter-arrival times of
  1 to 4 seconds), it is useful to have a few short rules instead of a
  longer single rule.

\item Figure~\ref{u-variance-figure}
  shows that the best sequence performs better than the best
  single rule as the variance of the arrival time increases.\footnote{
The performance of the 50\% rule is flat because the
uniform distributions used in this experiment have fixed mean and
are symmetric, so that the 50\% rule is always the rule that runs for
20 seconds. The 90\% rule changes with the variance, and the curve
exhibits some discretization effects. These could be eliminated using a
finer-grained set of rules.}
  The
  performance of the optimal sequence also appears to be
  largely unaffected by variance. This is exactly the behaviour
  we expect to observe --- the ability to run a sequence of rules
  instead of committing to a single one gives it robustness in the
  face of increasing variance. Since realistic environments
  can involve unexpected demands of many kinds, the possession
  of a variety of default behaviours of graded sophistication
  would seem to be an optimal design choice for a bounded agent.

\end{itemize}



\section{Learning Approximately Bounded-Optimal Programs}\label{learning-section}

The above derivations assume that a suitable rule set $\R$ is
available {\em ab initio}, with correct qualities $q_i$ and runtimes
$t_i$, and that the deadline distribution is known. In this section,
we study ways in which some of this information can be learned,
and the implications of this for the bounded optimality of
the resulting system. We will concentrate on learning rules and their
qualities, leaving runtimes and deadline distributions for future
work.

The basic idea is that the learning algorithms will converge, over
time, to a set of optimal components --- the most accurate rules and
the most accurate quality estimates for them. As this happens, the
value of the agent constructed from the rules, using the quality
estimates, converges to the value of $\lopt$. Thus there are two
sources of suboptimality in the learned agent:
\begin{itemize}
\item The rules in $\R$ may not be the best possible rules --- they
may recommend actions that are of lower utility than those that would
be recommended by some other rules.
\item There may be errors in
% {\em actual} utility of using a rule in a given episode may
% differ from the {\em expected} utility, giving rise to errors in
% the estimated 
estimating the expected utility of the rule. This can cause the
algorithms given above to construct suboptimal sequences, even if the
best rules are available.
\end{itemize}


Our notional method for constructing bounded optimal agents (1) learns sets
of individual decision procedures from episodic interactions, and (2)
arranges them in a sequence using one of the algorithms described
earlier so that the performance of an agent
using the sequence is at least as good as that of any other such
agent. We assume a parameterized learning algorithm $L_{{\cal J},k}$ that
will be used to learn one rule for each possible 
runtime $k \in \{1,\ldots, t_M\}$. Since there is never a need to include 
two rules with the same runtime in the $\R$, this obviates the need
to consider the entire rule language ${\cal J}$ in the optimization 
process.

Our setting places somewhat unusual requirements on the learning
algorithm. Like most learning algorithms, $L_{{\cal J},k}$ works by
observing a collection $T$ of training episodes in $\E$, including the
utility obtained for each episode. We do not, however, make any
assumptions about the form of the {\em correct} decision rule.
Instead, we make assumptions about the hypotheses, namely that they
come from some finite language ${\cal J}_k$, the set of programs in
${\cal J}$ of complexity at most $k$.  This setting has been called
the {\em agnostic learning} setting by Kearns, Schapire and Sellie (1992),
because no assumptions are made about the environment at all.
It has been shown (Theorems 4 and 5 in Kearns, Schapire and Sellie,
1992) that, for some languages ${\cal J}$, the error in the learned
approximation can be bounded to within $\epsilon$ of the best rule in
${\cal J}_k$ that fits the examples, with probability $1 - \delta$.
The sample size needed to guarantee these bounds is polynomial in the
complexity parameter $k$, as well as $\frac{1}{\epsilon}$ and
$\frac{1}{\delta}$.


In addition to constructing the decision procedures, $L_{{\cal J},k}$
outputs estimates of their quality $q_i$. 
Standard Chernoff-Hoeffding bounds can be
used to limit the error in the quality estimate to be within
$\epsilon_q$ with probability $1 - \delta_q$. The sample size for the
estimation of quality is also polynomial in $\frac{1}{\epsilon_q}$ and
$\frac{1}{\delta_q}$.

Thus the error in each agnostically learned rule is bounded to within
$\epsilon$ of the best rule in its complexity class with probability
$1 - \delta$. The error in the quality estimation of these rules is
bounded by $\epsilon_q$ with probability $1 - \delta_q$. From these bounds,
we can calculate a bound on the utility deficit in the agent program
that we construct, in comparison to $\lopt$:

\begin{theorem}
Assume an architecture $M_{{\cal J}}$ that executes sequences of decision
procedures in an agnostically learnable language ${\cal J}$ whose runtimes range over $[1..t_M]$.
For real time task environments with fixed time cost, fixed deadline, and
stochastic deadline, we can construct 
a program
$l$ such that 
\[V(\lopt,M,\E) - V(l,M,\E) \leq \epsilon + 2\epsilon_q\]
with
probability greater than $1 - m(\delta + \delta_q)$, where $m$ is the number of decision procedures in $\lopt$.
\end{theorem}

\noindent {\bf Proof:} We prove this theorem for the stochastic
deadline regime, where the bounded optimal program is a sequence of
decision procedures. The proofs for the fixed cost and fixed deadline
regimes, where the bounded optimal program is a singleton, follow as a
special case.  Let the best decision procedures for $\E$ be the set
$\R^* = \{{r_1}^*, \ldots, {r_n}^*\}$, and let $\lopt =  {s_1}^* \ldots
{s_m}^*$ be an optimal sequence constructed from $\R^*$.  Let $\R =
\{r_1, \ldots r_n\}$ be the set of decision procedures returned by the
learning algorithm.  With probability greater than $1 - m\delta$,
$q_i^* - q_i \leq \epsilon$ for all $i$, where $q_i$ refers to the {\em true}
quality of $r_i$. The error in the {\it estimated} quality $\hat q_i$ of
decision procedure $r_i$ is also bounded: with probability greater
than $1 - m\delta_q$, $|\hat q_i - q_i| \leq \epsilon_q$ for all $i$.

Let $s = s_1 \ldots s_m$ be those rules in $\R$ that 
come from the same  runtime classes as the rules
${s_1}^* \ldots {s_m}^*$ in $\R^*$.
Then, by Equation~\ref{stochastic-value-def}, we have
\[ 
V(\lopt,M,\E) - V(s,M,\E) \leq \epsilon
\]
because the error in $V$ is a weighted average of the errors in the individual
$q_i$.
Similarly, we have
\[
|\hat V(s,M,\E) - V(s,M,\E)| \leq \epsilon_q 
\]
Now suppose that the sequence construction algorithm applied to $\R$ produces
a sequence $l = {s_1}^{'} \ldots {s_l}^{'}$. By definition, this sequence
{\em appears} to be optimal according to the estimated value 
function $\hat V$. Hence
\[ \hat V(l,M,\E) \geq 
   \hat V(s,M,\E) \]
As before, we can bound the error on the estimated value:
\[
|\hat V(l,M,\E) -  V(l,M,\E)| \leq \epsilon_q 
\]
Combining the above inequalities, we have
\[ V(\lopt,M,\E) - V(l,M,\E) \leq \epsilon + 2 \epsilon_q \]
$\Box$


Although the theorem has practical applications, it is mainly intended
as an illustration of how a learning procedure can converge on a 
bounded optimal configuration.
With some additional work, more general error bounds can be derived
for the case in which the rule execution times $t_i$ and the real-time
utility variation (time cost, fixed deadline, or deadline
distribution) are all estimated from the training episodes.
We can also obtain error bounds for the case in which the rule language 
${\cal J}$ is divided up into a smaller number of coarser runtime classes,
rather than the potentially huge number that we currently use.


\section{Asymptotic Bounded Optimality}\label{abo-section}

The strict notion of bounded optimality may be a useful philosophical
landmark from which to explore artificial intelligence, but it may be
too strong to allow many interesting, general results to be obtained.
The same observation can be made in ordinary complexity theory:
although absolute efficiency is the aim, asymptotic efficiency is the
game.  That a sorting algorithm is $O(n\log n)$ rather than $O(n^2)$ is
considered significant, but replacing a ``multiply by 2'' by a
``shift-left 1 bit'' is not considered a real advance. The slack
allowed by the definitions of complexity classes is essential in building on earlier results, in
obtaining robust results that are not restricted to specific
implementations, and in analysing the
complexity of algorithms that use other algorithms as subroutines.  In
this section, we begin by reviewing classical complexity. We then
propose definitions of asymptotic bounded optimality that
have some of the same advantages, and show that classical optimality
is a special case of asymptotic bounded optimality.  Lastly, we report
on some preliminary investigations into the use of asymptotic bounded
optimality as a theoretical tool in constructing universal real-time
systems.

\subsection{Classical complexity}

A {\em problem}, in the classical sense, is defined by a pair of
predicates $\phi$ and $\psi$ such that output $z$ is a solution for
input $x$ if and only if $\phi(x)$ and $\psi(x,z)$ hold. A {\it
problem instance} is an input satisfying $\phi$, and an algorithm for
the problem class always terminates with an output $z$ satisfying
$\psi(x,z)$ given an input $x$ satisfying $\phi(x)$. Asymptotic
complexity describes the growth rate of the worst-case runtime of an
algorithm as a function of the input size. We can define this formally
as follows. Let $T_a(x)$ be the runtime of algorithm $a$ on input $x$,
and let $\wT_a(n)$ be the maximum runtime of $a$ on any input of size
$n$. Then algorithm $a$ has complexity $O(f(n))$ if
\[
\exists k,n_0\ \forall n\ n>n_0 \Rightarrow \wT_a(n) \leq kf(n)
\]
Intuitively, a classically optimal algorithm is one that has the
lowest possible complexity.
For the purposes of constructing an asymptotic notion of bounded
optimality, it will be useful to have a definition of classical
optimality that does not mention the complexity directly. This can
be done as follows:
\begin{definition}\label{copt-defn}{Classically optimal algorithm}: 
An algorithm $a$ is classically optimal if and only if
\[
\exists k,n_0\ \forall a',n\ n>n_0 \Rightarrow \wT_a(n) \leq
k\wT_{a'}(n)
\]
\end{definition}
To relate classical complexity to our framework, we will need to
define the special case of task environments in which traditional
programs are appropriate. In such task environments, an input is provided
to the program as the initial percept, and the utility function
on environment histories obeys the following constraint:
\begin{definition}\label{cenv-defn}{Classical task environment}:
$\langle E_P,U \rangle$ is a classical task environment for problem $P$ if
\begin{eqnarray*}
V(l,M,E_P) & = & \left\{ \begin{array}{l l}
                     u(T(l,M,E_P)) & \mbox{ if $l$ outputs a correct
                     solution for $P$} \\
                     0 & \mbox{ otherwise}
                   \end{array} \right.
\end{eqnarray*}
where $T(l,M,E_P)$ is the running time for $l$ in $E_P$ on $M$, $M$ is
a universal Turing machine, and $u$
is some positive decreasing function.
\end{definition}
The notion of a {\em problem class} in classical
complexity theory thus corresponds to a class of classical
task environments of unbounded complexity. For example, the Traveling
Salesperson Problem contains instances with arbitrarily large
numbers of cities. 


\subsection{Varieties of asymptotic bounded optimality}

The first thing we will need is a complexity measure on environments.
Let $n(E)$ be a suitable measure of the complexity of an
environment. We will assume the existence of environment classes that
are of unbounded complexity.  Then, by analogy with the definition
of classical optimality, we can define a worst-case notion of
asymptotic bounded optimality (ABO). Letting $\wV(l,M,n,\E)$ be the
minimum value of $V(l,M,E)$ for all $E$ in $\E$ of complexity $n$, we have
\begin{definition}\label{wabo-defn}{Worst-case asymptotic bounded optimality}:
an agent program
$l$ is timewise (or spacewise) worst-case asymptotically bounded optimal in $\E$
on $M$ iff 
\[\begin{array}{l}
\exists k,n_0\ \forall l',n\ \; n>n_0 \Rightarrow \wV(l,kM,n,\E) \geq
\wV(l',M,n,\E)
\end{array}\] 
where $kM$ denotes a
version of the machine $M$ speeded up by a factor $k$ (or with $k$
times more memory).
\end{definition}
In English, this means that the program is basically along the right
lines if it just needs a faster (larger) machine to have worst-case
behaviour as good as that of any other program in all environments.


If a probability distribution is associated with the environment class
$\E$, then we can use the expected value $V(l,M,\E)$ to define an
average-case notion of ABO:
\begin{definition}\label{aabo-defn}{Average-case asymptotic bounded optimality}:
an agent program
$l$ is timewise (or spacewise) average-case asymptotically bounded optimal in $\E$
on $M$ iff 
\[\begin{array}{l}
\exists k\ \forall l'\ V(l,kM,\E) \geq V(l',M,\E)
\end{array}\] 
\end{definition}
For both the worst-case and average-case definitions of ABO,
we would be happy with a program that was
ABO for a nontrivial environment on a nontrivial architecture $M$,
unless $k$ were enormous.\footnote{%
The classical definitions allow for optimality up to a constant factor
$k$ in the runtime of the algorithms.  One might wonder why we chose
to use the constant factor to expand the machine capabilities, rather
than to increase the time available to the program. In the context of
ordinary complexity theory, the two alternatives are exactly
equivalent, but in the context of general time-dependent utilities,
only the former is appropriate. It would not be possible to simply
``let $l$ run $k$ times longer,'' because the programs we wish to
consider control their own execution time, trading it off against
solution quality. One could imagine slowing down the entire
environment by a factor of $k$, but this is merely a less realistic
version of what we propose.}
In the rest of the paper, we will use the worst-case definition of
ABO. Almost identical results can be obtained using the average-case
definition.

The first observation that can be made about ABO programs is that
classically optimal programs are a special case of ABO programs:\footnote{This
connection was suggested by Bart Selman.} 
\begin{theorem}
  A program is classically optimal for a given problem $P$ if and only if
  it is timewise worst-case ABO for the corresponding classical
 task environment class $\langle \E_P, U \rangle$.
\end{theorem}
This observation follows directly from
Definitions~\ref{copt-defn}, \ref{cenv-defn}, and~\ref{wabo-defn}.

In summary, the notion of ABO will provide the same degree of
theoretical robustness and machine-independence
for the study of bounded systems as asymptotic
complexity does for classical programs.
Having set up a basic framework,
we can now begin to exercise the definitions.


\subsection{Universal asymptotic bounded optimality}

Asymptotic bounded optimality is defined with respect to a specific
value function $V\!$. In constructing real-time systems, we would
prefer a certain degree of independence from the temporal variation in
the value function.  We can achieve this by defining a family ${\cal
  V}$ of value functions, differing only in their temporal variation.
By this we mean that the value function preserves the preference
ordering of external actions over time, with all value functions in
the family having the same preference ordering.\footnote{The value
  function must therefore be {\em separable} (Russell \& Wefald,
  1989), since this preservation of rank order allows a separate time
  cost to be defined. See chapter 9 of (Keeney \& Raiffa, 1976) for a
  thorough discussion of time-dependent utility.}

For example, in the fixed-cost regime we can vary the time cost $c$ to
generate a family of value functions; in the stochastic deadline case,
we can vary the deadline distribution $P_d$ to generate another family.
Also, since each of the three regimes uses the same quality measure
for actions, then the union of the three corresponding families is
also a family.  What we will show is that a single program, which we
call a universal program, can be asymptotically bounded-optimal
regardless of which value function is chosen within any particular
family.
\begin{definition}{Universal asymptotic bounded optimality (UABO)}:
  An agent program $l$ is UABO in environment class $\E$ on $M$ for the
family of value functions ${\cal V}$ iff $l$ is ABO in $\E$ on $M$ for every
$V_i \in {\cal V}$.
\end{definition}
A UABO program must compete with the ABO programs for every individual
value function in the family.
A UABO program is therefore a universal real-time solution for a given task.
Do UABO programs exist? If so, how can we
construct them? 

It turns out that we can use the scheduling construction
>from (Russell \& Zilberstein, 1991) to design UABO programs.
This construction was designed to reduce task environments with unknown interrupt
times to the case of known deadlines, and the same insight applies
here. The construction requires
the architecture $M$ to provide program concatenation
(e.g., the LISP {\tt prog} construct), a conditional-return construct,
and the null program $\Lambda$. 
The universal program $l_U$ has the form of a concatenation of
individual programs of increasing runtime, with an appropriate
termination test after each. 
It can be written as
\[l_U = [l_0 \cdot l_1 \cdots l_j \cdots ]\]
where each $l_j$
consists of a program and a termination test. The program part in
$l_j$ is any program in ${\cal L}_M$ that is ABO in $\E$ for a
value function $V_j$ that corresponds
to a fixed deadline at $t_d=2^j \epsilon$,
where $\epsilon$ is a time increment smaller than the execution time
of any non-null program in ${\cal L}_M$. 

Before proceeding to a statement that $l_U$ is indeed UABO, let us look
at an example. Consider the simple, sequential machine architecture
described earlier. Suppose we can select rules from a three-rule set
with $r_1 = (0.2,2)$, $r_2 = (0.5,5)$ and $r_3 = (0.7,7)$. Since the
shortest runtime of these rules is 2 seconds, we let $\epsilon=1$.
Then we look at the optimal programs $l_0,l_1,l_2,l_3,\ldots$ for the
fixed-deadline task environments with $t_d = 1,2,4,8,\ldots$. These are:
\[l_0 = \Lambda;\quad l_1 = r_1;\quad l_2 = r_1; \quad l_3 = r_3;\quad \ldots\]
Hence the sequence of programs in $l_U$ is
$[\Lambda,r_1,r_1,r_3,\ldots]$.

\begin{figure}[t]
\epsfxsize=0.8\textwidth
\centerline{\epsffile{uabo-profile.ps}}
\caption{Performance profiles for $l_U$ running on $4M$, and for
$\lopt$ running on $M$ }
\label{uabo-figure}
\end{figure}

Now consider a task environment class with a value function $V_i$
that specifies a stochastic deadline uniformly distributed
over the range [0\ldots 10]. For this class,
$\lopt = r_1r_2$ is a bounded optimal sequence.\footnote{Notice that,
in our simple model, the output quality of a rule depends only on its
execution time and not on the input complexity. This also means that
worst-case and average-case behaviour are the same.}
It turns out that
$l_U$ has higher utility than $\lopt$ provided it is run on a
machine that is four times faster. We can see this by plotting the
two performance profiles: $Q_U$ for $l_U$ on $4M$ and $\Qopt$
for $\lopt$ on $M$. $Q_U$ dominates $\Qopt$, as shown in
Figure~\ref{uabo-figure}.

To establish that the $l_U$ construction yields UABO programs in
general, we need to define a notion of worst-case performance profile.
Let $\wQ(t,l,M,n,\E)$ be the minimum value obtained by interrupting $l$
at $t$, over all $E$ in $\E$ of complexity $n$. We know that each
$l_j$ in $l_U$ satisfies the following:
\[
\forall l',n\ n>n_j \Rightarrow \wV_j(l_j,k_j M,n,\E) \geq \wV_j(l',M,n,\E)
\]
for constants $k_j$, $n_j$. The aim is to prove that
\[
\forall V_i\in {\cal V}\ \exists k,n_0\ \forall l',n\ 
n>n_0 \Rightarrow \wV_i(l_U,kM,n,\E) \geq \wV_i(l',M,n,\E)
\]
Given the definition of worst-case performance profile,
it is fairly easy to show the following lemma (the proof is
essentially identical to the proof of Theorem 1 in Russell and
Zilberstein, 1991):
\newsavebox{\sbRZ}
\sbox{\sbRZ}{\parbox{\textwidth}{%
\begin{lemma}\label{RZ}
If $l_U$ is a universal program in $\E$ for ${\cal V}$,
and $l_i$ is ABO on $M$ in $\E$ for $V_i \in {\cal V}$,
then
$\wQ(t,l_U,kM,n,\E)$ dominates $\wQ(t,l_i,M,n,\E)$ for
$k\geq 4\,\max_j k_j$, $n>\max_j n_j$.
\end{lemma}%
}}


\noindent
\usebox{\sbRZ}
This lemma establishes that, for a small constant penalty, we can
ignore the specific real-time nature of the task environment in
constructing bounded optimal programs. However, we still need to deal
with the issue of termination. It is not possible in general for $l_U$
to terminate at an appropriate time without access to information
concerning the time-dependence of the utility function.
For example, in a fixed-time-cost task environment, the appropriate
termination time depends on the value of the time cost $c$.

For the general case with deterministic time-dependence, we can help
out $l_U$ by supplying, for each $V_i$, an ``aspiration level''
$\wQ_i(t_i,l_i,M,n,\E)$, where $t_i$ is the time at which $l_i$ acts.
$l_U$ terminates when it has completed an $l_j$ such that 
$q_j \geq \wQ_i(t_i,l_i,M,n,\E)$. By construction, this will happen no later
than $t_i$ because of Lemma~\ref{RZ}.

%% [[1. need aspiration levels for all $n$? 2. What is $t_i$ exactly?
%% Shortest time for any $E$ in $\E$ of complexity $n$?]]


\begin{theorem}
In task environments with deterministic time-dependence,
an $l_U$ with a suitable aspiration level is UABO in $\E$ on $M$.
\end{theorem}
With deadline heralds, the termination test is somewhat simpler and
does not require any additional input to $l_U$.
\begin{theorem}
In a task environment with stochastic deadlines, $l_U$ is UABO in $\E$
on $M$ if it terminates when the herald arrives.
\end{theorem}



\begin{figure}[t]
\epsfxsize=0.8\textwidth
\centerline{
\epsffile{abo.ps}
}
\caption{Throughput and accuracy improvement of  $l_U$ over  ~$\lopt^i$, as a function of mean arrival
time, $\lambda$ = 0.2, Poisson arrivals.}
\label{univ-figure}
\end{figure}

Returning to the mail-sorting example, it is fairly easy to see that
$l_U$ (which consists of a sequence of networks, like the optimal
programs for the stochastic deadline case) will be ABO in the
fixed-deadline regime. It is not so obvious that it is also ABO in any
particular stochastic deadline case --- recall that both regimes can
be considered as a single family.  We have programmed a constructor
function for universal programs, and applied it to the mail-sorter
environment
class. Varying the letter arrival distribution gives us different value
functions $V_i \in {\cal V}$.  Figure~\ref{univ-figure} shows that
$l_U$ (on $4M$) has higher throughput and accuracy than $\lopt^i$ across the
entire range of arrival distributions.




Given the existence of UABO programs, it is possible to consider the
behaviour of compositions thereof. The simplest form of composition is
functional composition, in which the output of one program is used as
input by another.  More complex, nested compositional structures can
be entertained, including loops and conditionals (Zilberstein, 1993).
The main issue in constructing UABO compositions is how to allocate
time among the components.  Provided that we can solve the time
allocation problem when we know the total runtime allowed, we can use
the same construction technique as used above to generate composite
UABO programs, where optimality is among all possible compositions of
the components. Zilberstein and Russell (1993), show that
the allocation problem can be solved in linear time in the size of the
composite system, provided the composition is a tree of bounded
degree.

\section{Conclusions And Further Work}\label{conclusion-section}

We examined three possible formal bases for artificial intelligence,
and concluded that bounded optimality provides the most appropriate
goal in constructing intelligent systems. We also noted that
similar notions have arisen in philosophy and game theory for more or
less the same reason: the mismatch between classically optimal
actions and what we have called {\em feasible} behaviours---those
that can be generated by an agent program running on a computing device
of finite speed and size.

We showed that with careful specification of the task environment and the
computing device one can design provably bounded-optimal agents.
We exhibited only very simple agents, and it is likely that
bounded optimality in the strict sense is a difficult goal to achieve
when a larger space of agent programs is considered.
More relaxed notions such as asymptotic bounded optimality (ABO) 
may provide more theoretically robust tools for further progress.
In particular, ABO promises to yield useful
results on composite agent designs, 
allowing us to separate the problem of designing complex ABO agents
into a discrete structural problem and a continuous temporal
optimization problem that is tractable in many cases.
Hence, we have reason to be optimistic that
artificial intelligence can be usefully characterized
as the study of bounded optimality.
We may speculate that provided the computing device
is neither too small (so that small changes in speed or size
cause significant changes in the optimal program design)
nor too powerful (so that classically optimal decisions
can be computed feasibly), ABO designs should be stable over
reasonably wide variations in machine speed and size
and in environmental complexity. The {\em details} of the optimal
designs may be rather arcane, and learning processes will
play a large part in their discovery; we expect that the focus of
this type of research will be more on questions of convergence to
optimality for various structural classes than on the end result itself.

Perhaps the most important implication, beyond the conceptual
foundations of the field itself, is that research on bounded
optimality applies, by design, to the
{\em practice} of artificial intelligence in a way that idealized,
infinite-resource models may not.  We have given, by way of
illustrating this definition, a bounded optimal agent: the design of a
simple system consisting of sequences of decision procedures that is
provably better than any other program in its class.  A theorem that
exhibits a bounded optimal design translates, by definition, into an
agent whose actual behaviour is desirable.

There appear to be plenty of worthwhile directions in which to
continue the exploration of bounded optimality. From a foundational
point of view, one of the most interesting questions is how the
concept applies to agents that can incorporate a learning component.
(Note that in section~\ref{learning-section}, the learning algorithm was
external to the agent.) In such a case, there will not necessarily
be a largely stable bounded optimal configuration if the agent program is not
large enough; instead, the agent will have to adapt to a shorter-term
horizon and rewrite itself as it becomes obsolete.

With results on the preservation of ABO under composition, we can
start to examine much more interesting architectures than the simple
production system studied above. For example, we can look at optimal
search algorithms, where the algorithm is constrained to apply a
metalevel decision procedure at each step to decide which node to
expand, if any (Russell \& Wefald, 1989).  We can also extend the work
on asymptotic bounded optimality to provide a utility-based analogue
to ``big-O'' notation for describing the performance of agent designs,
including those that are suboptimal.

In the context of computational learning theory, it is obvious that
the stationarity requirement on the environment, which is necessary to
satisfy the preconditions of PAC results, is too restrictive.  The
fact that the agent learns may have some effect on the distribution of
future episodes, and little is known about learning in such cases
(Aldous \& Vazirani, 1990). We could also relax the deterministic and
episodic requirement to allow non-immediate rewards, thereby making
connections to current research on reinforcement learning.


The computation scheduling problem we examined is interesting in
itself, and does not appear to have been studied in the operations
research or combinatorial optimization literature. Scheduling
algorithms usually deal with physical rather than computational
tasks, hence the objective function usually involves summation of
outputs rather than picking the best.  We would like to resolve the
formal question of its tractability in the general case, and also to
look at cases in which the solution qualities of individual processes
are interdependent (such as when one can use the results of another).
Practical extensions include computation scheduling for parallel
machines or multiple agents, and scheduling combinations of
computational and physical (e.g.,  job-shop and flow-shop) processes, 
where  objective functions are a combination of summation and
maximization. The latter extension  broadens the scope of applications
considerably.  An industrial process, such as designing and
manufacturing a car, consists of both computational steps (design,
logistics, factory scheduling, inspection etc.)  and physical
processes (stamping, assembling, painting etc.).  One can easily
imagine many other applications in real-time financial, industrial, and
military contexts.

It may turn out that bounded optimality
is found wanting as a theoretical framework. If this is the case,
we hope that it is refuted in an interesting way, so that a better framework
can be created in the process.





%\begin{small}
%\input{final.bbl}
 %\end{small}



\section*{Appendix: Additional Proofs}

%\resettheoremcounters

This appendix contains formal proofs for three subsidiary lemmata in
the main body of the paper.

%\begin{lemma}
%If $\forall t \ Q_{s_1}(t) \geq Q_{s_2}(t)$, then $V(s_1) \geq V(s_2)$.
%\end{lemma}
%\noindent {\bf Proof:}  follows directly from  
%Equation~\ref{stochastic-value-def}.$\Box$


\noindent\usebox{\sbqordering}

\noindent {\bf Proof:} Suppose this is not the case, and $s$ is
an optimal sequence. Then there must be two adjacent rules $i$, $i+1$
where $q_i > q_{i+1}$ (see
Figure~\ref{q-ordering}). Removal of rule $i+1$ yields a sequence $s'$
such that $Q_{s'}(t) \geq Q_{s}(t)$, from
Lemma~\ref{nondecreasing-profile} and the fact that $t_{i+2} \leq t_{i+1}
+ t_{i+2}$. By Lemma~\ref{dominating-profile},
$s'$ must also be optimal. We can repeat this removal process until
$s'$ is ordered by $q_i$, proving the theorem by reductio ad absurdum.$\Box$

\noindent\usebox{\sbaddbetter}

\noindent {\bf Proof:} We calculate $V(sz) - V(s)$ using
Equation~\ref{stochastic-value-def} and show that it is non-negative:
\begin{eqnarray*} 
V(sz) - V(s) & = & q_z[1 - P_d(({\textstyle \sum_{j=1}^{m} t_{j}}) + t_z)] - 
                   q_{m}[1 - P_d(({\textstyle \sum_{j=1}^{m} t_{j}}) + t_z)] \\ 
             & = & (q_z - q_{m})[1 - P_d(({\textstyle \sum_{j=1}^{m} t_{j}}) + t_z)]
\end{eqnarray*} 
which is non-negative since $q_z \geq q_{m}$.$\Box$

%\begin{corollary} 
%There exists an optimal sequence ending with the
%highest-quality rule in $\R$.
%\end{corollary}
%\noindent {\bf Proof:} Follows directly from 
%Lemma~\ref{addbetter}.

 
\begin{figure}[ht]
\epsfxsize=0.8\textwidth
\centerline{\epsfbox{q-ordering.ps}}
\caption{Proof for ordering by $q_i$; lower dotted line indicates 
original profile; upper dotted line indicates profile after removal 
of rule $i+1$.}
\label{q-ordering}
\end{figure}

\begin{figure}[ht]
\epsfxsize=0.8\textwidth
\centerline{\epsfbox{t-ordering.ps}}
\caption{Proof for ordering by $t_i$; dotted line indicates profile after removal of rule $i$.}
\label{t-ordering}
\end{figure}

\noindent\usebox{\sbtordering}

\noindent {\bf Proof:} Suppose this is not the case, and $s$ is
an optimal sequence. Then there must be two adjacent rules $i$, $i+1$
where $q_i \leq q_{i+1}$ and $t_i > t_{i+1}$ (see
Figure~\ref{t-ordering}). Removal of rule $i$ yields a sequence $s'$
such that $Q_{s'}(t) \geq Q_{s}(t)$, from
Lemma~\ref{nondecreasing-profile}. By Lemma~\ref{dominating-profile},
$s'$ must also be optimal. We can repeat this removal process until
$s'$ is ordered by $t_i$, proving the theorem by reductio ad absurdum.$\Box$




%\noindent\usebox{\sbRZ}
%
%\noindent {\bf Proof}: We must show that 
%\[\begin{array}{l}
%  \forall i \; \exists k \; \forall E \in \E \; V_i(l_U,kM,E)
%  \geq V_i(\lopt^i,M,E)
%\end{array}\] 
%Consider the situation just before the end of the $j^{th}$ program in $l_U$.
%The total execution time consumed by $l_U$ so far is $\leq (2^{j+1}
%-1)\epsilon/k$. The value of the best action obtained so far 
%is $V_i(l_{j-1},M,E)$. Therefore $l_U$ on $kM$ will return a better
%action than $\lopt^i$ on $M$ provided $k\geq 4$. $\Box$
%
%%\begin{theorem}:
%%In environments with deterministic time-dependence,
%%an $l_U$ with a suitable aspiration level is UABO in $\E$ on $M$.
%%\end{theorem}
%
%\begin{theorem}
%In an environment with stochastic deadlines, $l_U$ is UABO in $\E$
%on $M$ if it terminates when the herald arrives.
%\end{theorem}

\section*{Acknowledgements}

We would like to acknowledge stimulating discussions with Michael
Fehling, Michael Genesereth, Russ Greiner, Eric Horvitz, Henry Kautz,
Daphne Koller, and Bart Selman on the subject of bounded optimality; with Dorit
Hochbaum, Nimrod Megiddo, and Kevin Glazebrook on the subject of
dynamic programming for scheduling problems; and with Nick Littlestone
and Michael Kearns on the subject of agnostic learning. We would also
like to thank the reviewers for their many constructive suggestions.
Many of the early ideas on which this work is based arose in
discussions with the late Eric Wefald.  Thanks also to Ron Parr for
his work on the uniform-distribution case, Rhonda Righter for
extending the results to the exponential distribution, and Patrick
Zieske for help in implementing the dynamic programming algorithm. The
first author was supported by NSF grants IRI-8903146, IRI-9211512 and
IRI-9058427, by a visiting fellowship from the SERC while on
sabbatical in the UK, and by the NEC Research Institute. The second
author was supported by NSF grant IRI-8902721.

\vskip 0.2 in
%\bibliography{final}
%\bibliographystyle{theapa} 
\input{final.bbl}
\end{document}








