Provably Bounded Optimal Agents
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Distributed AI. Pages 338-344.
© 1993 International Joint Conferences on Artificial Intelligence
Abstract
A program is. bounded optimal for a given computational device for a given environment, if the expected utility of the program running on the device in the environment is at least as high as that of all other programs for the device. Bounded optimality differs from the decision-theoretic notion of rationality in that it explicitly allows for the finite computational resources of real agents. It is thus a central issue in the foundations of artificial intelligence. In this paper we consider a restricted class of agent architectures, in which a program consists of a sequence of decision procedures generated by a learning program or given a priori. For this class of agents, we give an efficient construction algorithm that generates a bounded optimal program for any episodic environment, given a set of training examples. The algorithm includes solutions to a new class of optimization problems, namely scheduling computational processes for real-time environments. This class appears to contain significant practical applications.
- Agre, P., and Chapman, D. (:1!987) Pengi: An imple- mentation of a theory of activity. In Proc. 6th National Conference on Artificial Intelligence, Seattle, WA: Mor- gan Kaufmann.
- Breese, J. S., and. Fehling, M. R. (1990) Control of problem-solving: Priaciples ud architectue. In Sha.chter, R. D., Levitt, T., Kanal, L., aad Lemmer, J. (Eds.) Uncertainty in Artificial Intelligence+. AJ:DS.. terdam: North Holland.
- Brooks, R. A. (1986) A robut, layered control system for a mobile robot. JEEE Journal oJ Robotic.s and Au- tomation, 2(1}, 14-23.
- Cherniak, C. (1986) Minimal rationality. Cambridge: MIT Press.
- 5} Dean, T . and Boddy, M. (1988) An analysis of time- dependent planning. In AAAI-88, 49-54.
- Dennett, D. (1986) The moral fir.st aid manual. Tanner lectures on human values, University of Michigan.
- Doyle, J. (1983) What is ra:\ional psychology? Toward a modern mental philosophy. AI Magazine 4 (3), 50-53.
- Etzioni. Tractable decision-analytic control. Proc. of 1st International Conference on Knowledge Representa- tion and Reasoning, 114-125, 1989.
- 9} Fehling, M., and Russell, S. J. {Eds.) (19~9) Prcx:eedi~g.s of the AAAI Spring Sympo.sium on L1m1ted Rabonal1ty. Stanford, CA.
- Good, I. J. {1971) Twenty-seven principles of rationality. In Godambe, V. P., and Sprott, D. A. (Eds.) Founda- tion.s of Stati.sticalinference. Toronto: Holt, Rinehart, Winston.
- Horvitz, E. J. (1988) Reasoning about beliefs and actions under computational resource constraints. In
- Levitt, T., Lemmer, J., and. Kanal, L. (Eds.) Uncertainty in Artificial Intelligence 9. Amsterdam: North Holland.
- Horvitz, E., Cooper, G., and Beckerman, D. {1989) Re- fl.ection and action under scarce resources: Theoretical principles and empirici!ol study. In Proceeding.s of the Eleventh International Joint Conference on Artificial In- telligence, Detroit, MI: Morgan Kaufmann.
- Kearns, M., Schapire, R., and Sellie, L. {1992) Toward efficient agnostic learning. In Proc. 5th Ann. Work.shop on Computational Learning Theory. Pittsburgh, PA: Morgan Kaufmann.
- 14} McCarthy, J. (1958) Programs with common sense. In Proceeding.s of the Sympo.sium on the Mechanization of Thought Proce.s.se.s, Teddington, England: HMSO.
- Newell, A. {1981) The knowledge level. AI Magazine 2, 1-20.
- Nilsson, N. J. (1991} Logic and artificial intelligence. Artificial Intelligence 45, 31-56.
- Russell, S. J., and Subramanian, D. (1992) On provably rational agents with limited performance hardware. In
- Baum, E. (Ed.) Computational learning and cognition: Proceeding' of the Third NEG Sympo.sium, SIAM Press.
- RuSIIdJ., S. J., and Wefald, E. H. {1989) Principles of metareasoning. In Proc. KR-89.
- Rusaell, S. J., and Wefald, E. H. {1991) Do the right th;ng: StudieJJ in limited rationality. Cambridge, MA: MIT Press.
- Russell, S. J., aDd Zilberstein, S {1991) Composing real- time systems. ID Proc. JJCAI-91, Sydney.
- 21}' Sav~e, L. J. (1972) The foundation.s of .statiJJtic.s, 2nd rev . ed. New York: Dover.
- Simon, H. A. (1976) On how to decide what to do. In [23}.
- Simon, H. A. (1982) Model.s of bounded rationalit11, Vol- ume 2. Cambridge: MIT Pre88.
- 24} Valiant, L. G. {1984) A tla.eory of the learnable. Com- munication.s of the A CM 18(11 }, 1134-42.
- von Neumann, J., and Morgenstern, 0 . (1947) Theory of game.s and economic beluwior. Princeton: Princeton University Press.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Since before the beginning of artificial intelligence, philosophers and economists have looked for a satisfac tory definition of rational behaviour. This is needed to underpin theories of ethics, inductive learning, reason ing, decision-making and economic modelling. Doyle [7] has proposed that AI itself be defined as the compu tational study of rational behaviour. The decision theoretic definition of rational behaviour as maximiza tion of expected utility, and analogous definitions in the context of logical planning, have been extremely valu able in allowing AI research to be done at an abstract level, independent of specific implementations. Several systems can already be said to satisfy the required input output relations.
Unfortunately, these approaches are of limited value because they ignore the total impracticality of reaching optimal decisions in realistic situations. In this paper, we propose instead the concept of bounded optimality University of California, Berkeley Ronald Parr CA 94 720, USA
parr~guard.berkeley.edu
in which the utility of a decision is a function of both its quality and the time taken to choose it. We give a formal definition below; informally, we say that an agent exhibits bounded optimality if its program is a solution to the constrained optimization problem presented by its architecture.
We begin in section 2 with a necessarily brief dis cussion of the relationship between bounded optimality and earlier notions of rationality. We note in particular that some important distinctions can be missed with out precise definitions of terms. Thus in section 3 we introduce formal definitions of agents1, their programs, their behaviour and their rationality. Section 4 exam ines a class of agent architectures for which the prob lem of generating bounded optimal configurations is ef ficiently soluble. The solution involves a new class of interesting and practically-relevant optimization prob lems. We examine several types of episodic, real-time environments and derive bounded optimal programs for these regimes. Finally, we describe a set of open theo retical and experimental issues, including an asymptotic version of bounded optimality that may be more robust and tractable than the strict version.
2 Historical perspective
The classical idea of perfect rationality, which developed from Mill's utilitarianism, was put on a formal footing in von Neumann's decision theory [25] . It stipulates that a rational agent always act so as to maximize its expected utility. The expectation is taken according to the agent's own beliefs; thus, perfect rationality does not require ommsc1ence.
In artificial intelligence, the logical definition of ra tionality, known in philosophy as the "practical syllo gism", was put forward by McCarthy [14], and reiterated strongly by Newell [15]. 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. 2
1 We use the term ralph (rational agent with limited perfor mance hardware) to denote an agent that exhibits bounded optimality.
2 This is not to say that this was the wrong approach at the time. McCarthy believed, probably correctly, in the halcyon
Economists have used rationality as an abstract model of economic entities, for the purposes of economic fore casting and designing market mechanisms. Unfortu nately, as Simon [23] pointed out, real economic enti ties have limited time and limited powers of delibera tion. He proposed the study of bounded rationality, in vestigating " ... the shape of a system in which effec tiveness in computation is one of the most important weapons of survival." Simon's work focussed mainly on satisficing designs, which deliberate until reaching some solution satisfying a preset "aspiration level." The re sults have descriptive value for modelling various actual entities and policies, but no prescriptive framework for bounded rationality was developed.
I. J. Good [10] emphasized the conceptual distinc tion between classical or "type I" rationality, and what he called "type II" rationality, or the maximization of expected utility taking into account deliberation costs. 3 What this means is that an agent exhibits type II ra tionality if at the end of its deliberation and subsequent action, its subjective utility is maximized compared to all possible deliberate/act pairs in which it could have engaged. Good does not define the space of possible de liberations, but from his informal descriptions, it is clear that Type II rationality is intended to prescribe optimal sequences of computational steps. Unfortunately, these may be even harder to select than actions themselves.
Recognizing these problems, Cherniak [4] suggested a definition of "minimal rationality", specifying lower bounds on the reasoning powers of any rational agent, instead of upper bounds. A philosophical proposal gen erally consistent with the notion of bounded optimality can be found in Dennett's "Moral First Aid Manual" [6].
Many researchers in AI, some of whose work is dis cussed below, have worked on the problem of designing agents with limited computational resources; the 1989 AAAI Symposium on AI and Limited Rationality [9] contains an interesting variety of work on the topic.
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 anytime [5] or flexible algorithms [11], that return better results as time goes by, a simple form of metareasoning allows an agent to behave well in a real-time environment. Breese and Fehling [2] apply similar ideas to controlling multiple de cision procedures. Russell and Wefald [18] give a general method for precompiling certain aspects of metareason ing 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 Type II rationality; they pro vide 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.
days before formal intractability results in computation were known, that in the early stages of the field it was important to concentrate on "epistemological adequacy" before "heuristic adequacy".
3 Simon [22] also says: "The global optimization problem is to find the least-cost or best-return decision, net of com putational costs."
Horvitz [11] uses the term bounded optimality to re fer to "the optimization of computational utility given a set of assumptions about expected problems and con straints in reasoning resources." Russell and Wefald [19] say that an agent exhibits bounded optimality "if its program is a solution to the constrained optimization problem presented by its architecture." The philosophi cal "move" , from optimizing over actions or deliberation sequences to optimization over programs, is the key to our proposal. 4 In reality, designers of intelligent agents do not have direct control over the agent's actions or deliberations; these are generated by the operation of the agent's program. Prescriptive specification of ac tions (Type I) or deliberations (Type II) may produce impossible constraints, if these specifications are not re alized by any program for the agent. Precise definition of the space of agent programs is therefore an important part of the study of bounded optimality. 5 In the next section, we build a suitable set of definitions from the ground up, so that we can begin to demonstrate exam ples of provably bounded optimal agents.
3 Agents, architectures and programs
Intuitively, an agent is just a physical entity that we wish to view in terms of its perceptions and actions. What counts in the first instance is what it does, not necessar ily what it thinks, or even whether it thinks at all. This initial refusal to consider further constraints on the inter nal workings of the agent (such as that it should reason logically, for example) helps in three ways: first, it al lows us to view such 'cognitive faculties' as planning and reasoning as occurring in the service of finding the right thing to do; second, it makes room for those among us [1; 3] who take the position that systems can do the right thing without such cognitive faculties; third, it allows more freedom to consider various specifications, bound aries and interconnections of subsystems.
An agent can be described abstractly as a mapping (the agent function) from percept sequences to actions; this mapping is implemented by an agent program. The design and evaluation of agents are based on the be haviour of the agent program in an environment.
Let P 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. Then we have
Definition 1 Agent function: a mapping
where p· is the set of all possible percept sequences. The agent function is an entirely abstract entity, unlike the agent program. Computability theory relates these abstract functions to their finite representations as pro grams running on a machine.
'This move is analogous to the development of 'rule util itarianism' from 'act utilitarianism'.
5 Recent work by Etzioni [8] and Russell and Zilber stein [20] can be seen as optimizing over a well-defined set of agent designs.
We will consider a physical agent as consisting of an architecture and a program. The architecture is respon sible for interfacing between the program and the dis crete, deterministic environment, and for running the program itself. With each architecture M, we associate a finite programming language LM, which is just the set of all programs runnable by the architecture. An agent program is a program I E LM. When a sequence of per cepts is provided by the architecture to the program, a sequence of actions is generated: the ith action occurs between percept i and percept i + 1. Thus an architec ture maps a percept sequence of length k, for any k, to an action sequence of the same length according to the program it is running. The behaviour of an agent is the sequence of actions it generates.
Definition 2 Architecture: a fixed interpreter M for the agent's program:
For the purposes of this paper, we will define the envi ronment as a set of world states together with mappings defining the effects of actions and the generation of per cepts:
Definition 3 Environment: a set of world states W and mappings
It is important to note that although every program induces a mapping in the above sense, the action fol lowing a given percept is not necessarily the agent's "re sponse" to that percept; because of the delay incurred by deliberation, it may only reflect percepts occurring much earlier in the sequence, and it may not be possible to associate each action with a particular prior percept sequence.
3.1 Bounds on rationality
The expected utility of an action A; that has possible outcomes W;j, for an agent with prior evidence E about the environment, is given by
where U is a real-valued utility function on states.
Definition 4 Perfect rationality: an agent is perfectly rational iff it selects action A = argmax; V(A; ), so as to maximize its expected utility.
This definition is a persuasive specification of the agent function f and underlies several current projects in intelligent agent design. 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.
By neglecting the fact of limited resources for compu tation, classical decision theory fails to provide an ad equate theoretical basis for artificial intelligence. The 'finitary predicament' [4] arises because real agents have only finite computational power and because they don't have all the time in the world. 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 con centrated on specifying an optimal agent function /opt in order to guarantee the selection of the best possible action A in each situation. The function /opt is indepen dent of the architecture M. Unfortunately, the behaviour of any program that implements this function may not be desirable. The delay in computing /opt ( P1, ... , Po~:) means that the k'h action may be optimal only with respect to some much earlier subsequence, and is now totally inappropriate.
3.2 Bounded optimality
To escape this quandary, we propose a machine dependent standard of rationality, in which optimality constraints are imposed on programs rather than agent functions, deliberations or behaviours. To formalize this idea, it will be helpful to assume a real-valued util ity function U on histories, that is, sequences of world states. Then we assign values to a program I based on the sequence of states through which it "drives" the en vironment E when run on .M starting in the world W0 :
where result denotes the state sequence generated by the execution of the program I, defined in the obvious way using TA and Tp.
If the initial state Wo and environment E are known, then the optimal agent program is given by:
Definition 5 Optimal agent program:
If instead the "designer" has only a probability distribu tion over the initial state and environment model, then this will introduce a distribution over the state sequences generated, and the optimal program has the highest ex pected value V(l, M, E) over this distribution.
4 Provably ralphs
In order to construct a provably rational agent with lim ited performance hardware (ralph), we must carry out the following steps:
- Specify a class of machines on which programs are to be run.
- Specify the properties of the environment in which actions will be taken, and the utility function on the behaviours.
- Propose a construction method.
- Prove that the construction method succeeds m building ralphs.
4.1 Production system architectures
We begin our study with a simple form of production system, in which condition-action rules of t?e form "If t/J; then do Ai " are applicable whenever theu left-ha~d sides become true. Even such a simple system can easily overtax the resources of a real-time agent, if the rule base becomes large and the conditions become complex. An agent implemented as a producti~n system ~ill the~efore contain approximate rules, for which the actiOn Ai I~ ~ot guaranteed to be the best possible whenever condition tPi obtains in the world.
An illustrative example is provided by the image pro cessing algorithms in an automated mail sorter. Thes~ machines scan handwritten or printed addresses on mrul pieces and dispatch them accordingly. The scanned im age is processed by any or all of several procedures de signed to read with varying degrees of accuracy and re source expenditure; each procedure may have many pos sible variants - for example, we can vary the number of hidden nodes in a neural network recognizer. To prevent jams, the mail piece must be so~ted a~propriately, or rejected, in time for the (stochastic) amval of the next piece. The object is to maximize the accuracy of .s~rt ing while minimizing the reject percentage and av01dmg jams.
Here we consider only a special case of production system, in which complete rules (or decision rules) are matched in a fixed sequence. We call a sequence of pro duction rules a strategy. Each rule i has associated with it a match time ti and a quality qi, which corresponds to the utility of the rule's recommended action if taken at the beginning of the episode.
We assume that each rule is drawn from some rule language :J. (In keeping with the scheduling literature, we will often use the term "job" to refer to a rule in a sequence.) Let M:r n denote a production system archi 'tecture that can ac~ommodate rules of maximum size n from rule language :1. For example, we might consider feedforward neural networks with at most n nodes.
In executing a typical sequence R = (ri .. . rm}, the agent matches each rule in turn agai~t the current. per cept, generating a recommended actiOn. At some time t after the beginning of the episode, it will decide to act, selecting the highest-quality action recommended b! any of the rules it has previously matched. If the quality of the rule chosen is qi, the value of the episode for the agent will be some function of qi and t, _accordin~ to the regimes described below. Before the episode begms, the agent may not know when it will act (for ex~ple, in the stochastic deadline case), so generally speakmg the value of a given strategy will be an expectation.
4.2 Episodic real-time environments
First, we place some restrictions on the environment ~n order to simplify our problem. We need C to learn util ity information, so in order to avoid (te~po_rari~y), the credit assignment problem we assume an episodic en vironment, where after each non-null action by the agent, a reward is received and the environment then reaches an unknown state drawn from a probability distribution that remains stationary over time. The initial state Wo is also drawn from this distribution. In the mail-sorting example, the reward is 1 for a correct dispatch; 0 for an incorrect dispatch; 0.2, say, for a reject; and -oo for a jam.
In order to talk about deadlines and time cost, it is useful to have a notion of inaction. Let noop' denote a se quence of null actions lasting t time steps. Also, [A I ~] will denote the sequence of world states through which the action sequence A drives the environment given an initial state W . We use '·' to denote concatenation of sequences.
Now we can define three typical real-time regimes: fixed time cost, fixed deadline and stochastic deadline.
Definition 6 Fixed time cost: for any action A, any state W and any state sequences Wi, W;, U(Wi · W · [noop' ·A I W] · Wj) = U(Wi · W ·[A I W] · Wj)- ct. for some constant c.
Definition 7 Fixed deadline: for any action A, any state W, state sequences W;, Wi, for some constant Td, U(Wi · W · [noop' ·A I W] · Wj)
Deadlines are thus represented by a utility "cliff'' occur ring at some time Td after the beginning of an episode. In the case of a stochastic deadline, which describes the mail sorter, the location of the utility cliff is not known exactly. We assume that, for the designer, the value of [noop' I W] is a random variable, distributed in such a way that an action following it has probability P(t) of being of zero utility for the episode. This corresponds to P being the cumulative distribution function for the deadline arrival time. 6
4.3 The construction algorithm
Our general scheme at present is to exhibit an algo rithm that is capable of learning sets of individual de cision procedures, and arranging them in a sequence such that the performance of an agent using the se quence is at least as good as that of any other such agent. That is, the construction algorithm C, operat ing in E, returns a program I for architecture M such that V(l, M, E)~ V(/opt, M, E). C will work by first ?b serving a set e of training episodes in E, and then budd ing an approximately optimal strategy using a learning algorithm L:r,~:, for learning rules of size k in the rule language :r.
procedure C(n, e, P)
In addition to constructing the decision rules, L:r,1: outputs estimates of the rule quality qi. For now, we will assume that the rule match times ti and the dead line distribution P (for the stochastic case) are known. Algorithm optimize extracts an optimal strategy from the rule set R . In the following subsections we describe the three variants of optimize.
6 We assume that some percept immediately precedes the .actual deadline, a.lloting the agent to respond at the next .step. Without this, the agent is walking ·blindfolded towards the utility cliff (also an interesting problem).
4.4 Results for fixed time cost
This case is straightforward. The value of a strategy is given by
Theorem 1 The optimal strategy for fixed time cost utility functions is the singleton argmazieR[qi- cti].
4.5 Results for fixed deadline
This case is also straightforward. The value of a strategy sis given by:
Theorem 2 The optimal strategy is the singleton se quence i, where qi is the highest among all rules for which ti ~ Td.
4.6 Results for stochastic deadlines
With a stochastic deadline distributed according to P(t), the value of a strategy s = s1, .. . , Sm is an expectation. It is calculated as a summation, over the jobs that can be interrupted, of the probability of interruption times the quality of the best completed job:
where Mi = maz(q,,, .. . , q,;), and for convenience we define t,m+· = oo. We will use this formula to prove a number of properties of optimal strategies.
A simple example serves to illustrate the value func tion. Consider R = {r~, r2, ra} . The rule r1 has a quality of 0.2 and needs 2 seconds to r,un: we will represent this by r1 = (0.2, 2). The other rules are r2 = (0.5, 5), ra = (0.7, 7) . The deadline density func tion p (= dP/dt) is a uniform distribution over 0 to 10 seconds. The value of the sequence r1r2r3 is
A geometric intuition is given by the notion of a perfor mance pr·ofile shown in Figure 1. 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 pro file during the interval of length ti while job i is running is the quality of the best of the previous jobs.
The following lemma gives an extremely useful prop erty of optimal sequences:
Lemma 1 There exists an optimal sequence that is sorted in increasing order of qi.
Henceforth we need consider only q-ordered strategies. This means that Mi in equation (3) can be replaced by qi.
The following lemma establishes that a strategy can always be improved by the addition of a better job at the end:

Lemma 2 For every sequence s = s1 , .. · , Sm sorted in increasing order of quality, and single step z with qz ~ q,,.., V(sz) ~ V(s).
Corollary 1 There exists an optimal strategy ending with the highest-quality job in R .
Proofs of all the above results appear in [17].
4.6.1 A Dynamic Programming Algorithm
The dynamic programming method can be used to ob tain an optimal sequence of decision rules in pseudo polynomial time. We assume that the time ti associated with each rule is an integer (this is almost without loss of generality, using standard rounding and scaling meth ods). In keeping with the lemma above, we assume that optimal strategies are ordered by qi.
The algorithm constructs the tableS( i, T), where each entry in the table is the highest value of any sequence that ends with rule 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 = LieR ti . The update rule is:
From Corollary 1, we can read off the best sequence from the highest value in row n of the matrix M. ·
Theorem 3 The DP algorithm computes the optimal sequence in time 0( n 2 L) where n is the number of deci sion procedures in R.
Uniform distributions If the deadline is uniformly distributed over some initial interval, we can obtain an optimal sequence in strongly polynomial time. Initially, we assume an interval longer than any possible sequence. Then the probability that the deadline arrives during job Si of sequence s is just P(t,.) . Hence we have a simple recursive specification of the value V(as) of a sequence beginning with job a:
A dynamic programming algorithm can then use the state function s,(i), which is the highest value of any rule sequence ending in f and beginning with rule i. ~om lemma 1 and equation 4, the update rule for s,(i) lS
with boundary condition s, (f) = q! (1- P(t 1) ). For any given f , s, ( i) can therefore be tabulated for i = 1 .. . n in time O(n 2 ), from which we can obtain the optimal sequence.
If all the rules can fit before the end of the deadline distribution, then from Corollary 1 above the last rule f must be the rule with highest quality. Otherwise, any rule might be the last rule with a non-zero chance of completing, so we check each candidate:
Theorem 4 The optimal sequence of decision proce dures for a uniformly distributed stochastic deadline can be determined in O(n 3 ) time where n is the number of decision procedures in R .
4. 7 Agnostic Learning of Decision Rules
Our learning algorithm L:r,k searches for the best rule in .J, k. In order to work in any environment , it must be agnostic [13] in that it makes no assumptions about the target function, that is, the form of the correct de cision rule. It searches for the best subject to a com plexity parameter k that bounds the size of the rules. Kearns, Schapire and Sellie have shown (Theorems 4 and 5 in [13]) that, for some languages .J, the error in the learned approximation can be bounded to within i of the best rule in :J, k that fits the examples, with probability 1-6. The sample size needed to guarantee these bounds is polynomial in the complexity parameter k, as well as ~ and j-. Once an approximate rule with a certain com plexity k E { 1, . .. n} is learned, we statistically estimate its quality q. Standard Chernoff-Hoeffding bounds can be used to limit the error in the quality estimate to be within iq with probability 1-6q . The sample size needed is also polynomial in ..L and ~- £4 Gq
Thus the error in the agnostically learned rules is bounded to within i of the best rule in its complexity class with probability 1- 6. The error in the quality es timation of these rules is bounded by iq with probability 1 - 6q . We can show that the policy selection methods for the three real-time regimes will incur a deficit of at most i + 2iq in the choice of the optimal sequence of rules.
4.8 The bottom line
We can now state the bounded optimality theorem for our construction procedure.
Theorem 5 Assume a production system architecture M:r ,n, operating in any episodic environment. For each of the three real-time regimes defined above, with proba bility greater than 1 - 6 - 6q the construction procedure C returns a program I such that V(/opt)- V(l) < i+2iq after seeing . a number of episodes that is polynomial in n , ~ ~ f-, ~ and f-. Furthermore, the computation time 9 9 of C is (at worst) polynomial in the above quantities and in L , the sum of the rule execution times.
Although the theorem has practical applications, it is mainly intended as an illustration of the derivation of a bounded optimal agent . With some additional work, more general error bounds can be derived for the case in which the rule execution times ti and the real-time utility variation (time cost , fixed deadline or deadline distribu tion) are all estimated from the training episodes.
5 Further work
We plan to extend this work in several directions, as follows.
1. Foundational issues:
Learning agents: When the agent , whose design is to be optimized, includes a learning component, the notion of bounded optimality becomes even more interesting be cause we must take into account how the agent's config uration will evolve over time, reflecting its own expected obsolescence.
Asymptotic bounded optimality: The strict notion of bounded optimality may be a useful philosophical land mark from which to explore artificial intelligence, but it may be too strong to allow many interesting, general re sults to be obtained. Just as in complexity theory, where absolute efficiency is the aim but asymptotic efficiency is the game (so to speak), in studying bounded optimality an asymptotic version might help. First, we need a class of environments, E, which is unbounded in a complexity measure on environments n(E) . Then we will say that an agent program I is timewise asymptotically bounded optimal iff
where kM denotes a version of the machine M speeded up by a factor k . In English, this means that the pro gram is basically along the right lines if it just needs a faster machine to be as good as the best program on all problems above a certain level of difficulty.
Asymptotic bounded optimality generalizes the stan dard definition of asymptotic complexity. Let E be a class of environments in which a problem is input to the machine at time t = 0, where n(E) is the input size measure. Let V return 1/t (or any decreasing function oft) for a program that outputs the correct solution at timet , and 0 for all other programs. Then a program is bounded optimal iff it has asymptotic complexity equal to the tight lower bound for the class E . Note that in standard complexity, we allow any constant factor c in the execution time of the program, whereas our defini tion uses a constant factor in the speed of the machine. In the standard setting these are equivalent, but with more general time-dependent utilities only the latter is appropriate.
2. Scheduling issues:
The existence of polynomial-time algorithms and ap proximation schemes for variants of the computation scheduling problem; scheduling algorithms for situations in which the solution qualities of individual processes are interdependent (such as when one can use the results of another); scheduling combinations of computational and physical (e.g., job-shop and flow-shop) processes, where objective functions are a combination of summation and maximization; and computation scheduling for parallel machines or multiple agents.
9. Learning issues:
Relaxing the stationarity requirement on the environ ment- this entails generalizing the PAC model to han dle the case in which the fact that the agent learns ~ may have some effect on the distribution of future episodes; relaxing the episodic requirement. to allow no~ immediate rewards - this entails addressmg the credit assignment problem; examining varia~ts of the agnostic learning model to find the most practically useful theo retical scenario.
,/. Applications: . Despite the deliberate simplicity of the architecture, our construction algorithm can be applied directly to the problems such as scheduling image-processing algo rithms for a mail sorter. Scheduling of mixed eomputa tional and physical processes, mentioned above, broad ens the scope of applications considerably. An industrial process, such as designing and manufacturing ~ c~, con sists of both computational steps (design, logistics, fac tory scheduling, inspection etc.) and physical proc~ (stamping, assembling, painting etc.). One can e~ily imagine many other applications in real-time financial, industrial and military contexts.
6 Conclusions
In short we are proposing a new line of inquiry into bounded' optimal agents in which the value of a deci sion is judged in terms of the effect it has on the actions performed by the agent, noting that both actions and computations have time value. Bounded optimality may provide a suitable basis for theoretical research in ar tificial intelligence. Asymptotic bounded optimality in particular promises to yield useful results on composite agent designs, usin~ the optimality-preserving c?mp~si tion methods in [20j. As a robust measure of rationality, it's possible that it could do for AI what "big-0" de scriptions did for complexity theory.
Bounded optimality also has philosophically interest ing implications. For example, like the rule-utilitarians we no longer talk about rational actions, because indi vidual actions, and even deliberations, by a bounded op timal agent may be arbitraruy irrational in the classical sense.
Furthermore, this theoretical research should, by de sign, apply to the 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 condition action rule system that, given a learning mechanism, provably and efficiently converges to a rational config uration.
@inproceedings{ijcai1993p48,
title = {Provably Bounded Optimal Agents},
author = {Russell, Stuart J. and Subramanian, Devika and Parr, Ronald},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {338--344},
year = {1993},
note = {Distributed AI},
url = {https://ijcai.org/proceedings/1993/48},
}
TY - CPAPER TI - Provably Bounded Optimal Agents AU - Russell, Stuart J. AU - Subramanian, Devika AU - Parr, Ronald T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 338 EP - 344 UR - https://ijcai.org/proceedings/1993/48 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: