Provably Bounded-Optimal Agents
  Since its inception, artificial intelligence has relied upon a theoretical
foundation centered around 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 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, asymptotic bounded
optimality (ABO), that generalizes the notion of optimality in classical
complexity theory. We then construct 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.
