Provably Bounded Optimal Agents

Stuart J. Russell, Devika Subramanian, Ronald ParrIJCAI 1993 · OpenReview

Abstract

Since its inception, artificial intelligence has relied upon a theoretical foundation centred 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.

Introduction

In classical decision theory and early AI, a "rational" agent is defined as one that always chooses the action maximizing its expected utility. However, this definition ignores the "finitary predicament": real agents possess limited computational power and finite time. If an agent takes ten minutes to calculate the "perfect" move in a game of speed chess, it has already lost.

This paper addresses the gap between abstract, unachievable optimality and the practical reality of engineering agents. The authors argue that AI needs a theoretical foundation that accounts for computational costs. The challenge is to define what it means for an agent to be "optimal" when the time spent thinking is just as costly as a suboptimal action.

Theoretical Framework: Bounded Optimality

The authors propose bounded optimality as a more realistic goal. They define an agent as a combination of an architecture (the hardware/interpreter) and a program (the software). An agent is considered bounded-optimal if its program is the best possible program that can run on that specific architecture within a given environment.

This shift moves the unit of optimization from individual actions or deliberations to the program itself. Instead of asking "What is the best action now?", we ask "What is the best program to have running on this machine?"

Optimal Agent Construction

To demonstrate the feasibility of this framework, the authors focus on Production Systems—agents that use a sequence of "if-then" decision procedures. They analyze three distinct real-time regimes:

  1. Fixed Time Cost: Every unit of time spent thinking subtracts a constant amount from the final utility.
  2. Fixed Deadline: The agent has a hard cutoff; any action taken after the deadline yields zero utility.
  3. Stochastic Deadline: The deadline is a random variable, representing environments where the time available is unpredictable (e.g., a mail-sorting machine where the next letter arrives at an uncertain interval).
Figure 1: A step-function representation of a stochastic deadline distribution $P(t)$.

The core of their methodology is a two-step construction algorithm:

  • Agnostic Learning: A learning algorithm identifies a set of decision rules from training examples without making prior assumptions about the "true" underlying rule.
  • Dynamic Programming (DP): A novel DP algorithm sequences these learned rules into an optimal strategy. For stochastic deadlines, the authors prove that an optimal sequence should always test rules in order of increasing quality.

Key Insights: The "Ralph" and ABO

A significant contribution of this work is the Increasing Quality Lemma. In environments with unpredictable deadlines, the best strategy is to start with quick, low-quality "guesses" and gradually move toward more complex, higher-quality decision procedures. This ensures that the agent always has some answer ready if the clock runs out early.

The authors also introduce Asymptotic Bounded Optimality (ABO), a "Big-O" equivalent for AI rationality. A program is ABO if it is "basically along the right lines"—meaning it would be as effective as the best possible program if it were running on a slightly faster machine. Agents exhibiting bounded optimality are affectionately termed Ralphs (Rational Agents with Limited Performance Hardware).

Results and Evaluation

The paper provides several theoretical guarantees:

  • Efficiency: For a uniformly distributed stochastic deadline, the optimal sequence of decision procedures can be determined in $O(n^3)$ time, where $n$ is the number of available procedures.
  • Convergence: The construction algorithm $C$ is proven to be efficient. Given a polynomial number of training episodes relative to the complexity of the rules, the algorithm returns a near-optimal program for the given architecture.
  • Empirical Illustration: These results are illustrated using a simulated "automated mail sorter" environment, where agents must scan addresses and dispatch mail before the next piece arrives.

Discussion and Limitations

While this framework provides a rigorous foundation for bounded rationality, several challenges remain:

  • Architectural Complexity: The current proofs rely on restricted production systems. Real-world architectures are often parallel and significantly more complex.
  • Stationary Environments: The model assumes the environment remains constant. Future work must address non-stationary environments where an agent's learning might alter the distribution of future problems.
  • Credit Assignment: The research focuses on episodic environments to sidestep the complex problem of temporal credit assignment—determining which specific computation led to a later reward.

In conclusion, bounded optimality offers a promising path toward bridging the gap between AI theory and practice, providing a formal way to design agents that are "the best they can be" given their inherent limitations.

Summary updated

Abstract

Since its inception, artificial intelligence has relied upon a theoretical foundation centred 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.
BibTeX
@inproceedings{russell1993provably,
  author = {Stuart J. Russell and Devika Subramanian and Ronald Parr},
  title = {{Provably Bounded Optimal Agents}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1993},
  url = {https://openreview.net/forum?id=Skb-aXf_-S},
}
Figure