Provably Bounded-Optimal Agents

By Stuart J. Russell, Devika Subramanian. 1994

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Research Priorities for Robust and Beneficial Artificial Intelligence (2015, background): “Example research topics in this area include reasoning and decision under bounded computational resources à la Horvitz and Russell (Horvitz 1987; Russell and Subramanian 1995), how to take into account correlations between AI systems’ behaviors and those of their environments or of other agents (Ten”
A Minimum Relative Entropy Principle for Learning and Acting (2008, methodology): “A I] 1 Keywords: Artificial Intelligence, Minimum Relative Entropy Principle, Bayesian Control Rule, Interaction Sequences, Operation Modes.”
Reward is enough (2021, background): “The agent system α is limited by practical constraints to a bounded set [43].”
Bounded Optimal Exploration in MDP (2016, background): “We discuss the relationship to bounded rationality (Simon 1982) and bounded optimality (Russell and Subramanian 1995) as well as the corresponding notions of regret and average loss in the appendix of the extended version.”
Decision Theory with Resource-Bounded Agents (2013, background): “‡Supported in part by NSF grants IIS-0812045 and CCF-1214844, and AFOSR grants FA9550-08-1-0438 and FA9550-09-1-0266. we take the objects of choice in a decision problem to be Turing machines, and charge players for the “complexity” of the Turing machine chosen (e.g., its running time).”
Thermodynamics as a theory of decision-making with information-processing costs (2012, background): “Starting with Simon [23], bounded rationality has been extensively studied in psychology, economics, political science, industrial organization, computer science and artificial intelligence research—see for example [40, 41, 42, 43, 10, 11, 44, 45].”
A Roadmap of Agent Research and Development (2004, background): “In particular, such algorithms were predicated on the assumption of calculative rationality[126].”
Information-Theoretic Bounded Rationality (2015, background): “…computational costs [Zilberstein, 2008]; bounded optimality restricts the computational complexity of the programs implementing the optimal policy [Russell and Subramanian, 1995]; an approach that we might label procedural bounded rationality attempts to explicitly model the limitations in the…”
Doing more with less: meta-reasoning and meta-learning in humans and machines (2019, background): “notion of metalevel rationality into the concept of ‘bounded optimality’ that also takes into account the computational constraints on metareasoning itself [9,7].”
Space-Time Embedded Intelligence (2012, background): “In both Legg’s definition of intelligence [4] (based on AIXI [3]) and Russell’s bounded-optimality framework [10] (which embraces time and space constraints on the program of the agent), the agent is separated from the environment and therefore immortal.”
Efficiency of learning vs. processing: Towards a normative theory of multitasking (2020, background): “Research in artiﬁcial intelligence has suggested that such behavior is normative; that is, it may reﬂect bounded optimality , in which an agent maximizes reward per unit time given intrinsic limitations in its computational architecture (Russell & Subramanian, 1995).”