Provably Bounded-Optimal Agents

Abstract

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.

See http://www.jair.org/ for any accompanying files

References in corpus (1)

• Reasoning About Beliefs and Actions Under Computational Resource Constraints

Cited by in corpus (14)

• Thermodynamics as a theory of decision-making with information processing costs
• Density Encoding Enables Resource-Efficient Randomly Connected Neural Networks
• The Two Kinds of Free Energy and the Bayesian Revolution
• Information-Theoretic Bounded Rationality
• Reasoning, Metareasoning, and Mathematical Truth: Studies of Theorem Proving under Limited Resources
• Generalized Thompson Sampling for Sequential Decision-Making and Causal Inference
• Learning to select computations
• Extending Environments To Measure Self-Reflection In Reinforcement Learning
• Navigating the Trade-Off between Multi-Task Learning and Learning to Multitask in Deep Neural Networks
• Bounded Optimal Exploration in MDP
• Decision Theory with Resource-Bounded Agents
• Adaptive information-theoretic bounded rational decision-making with parametric priors
• Evolved preambles for MAX-SAT heuristics
• Error bounds on the probabilistically optimal problem solving strategy