Proceedings

Provably Bounded Optimal Agents

Download BibTeX Cite

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.

  1. 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.
  2. 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.
  3. 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.
  4. Cherniak, C. (1986) Minimal rationality. Cambridge: MIT Press.
  5. 5} Dean, T . and Boddy, M. (1988) An analysis of time- dependent planning. In AAAI-88, 49-54.
  6. Dennett, D. (1986) The moral fir.st aid manual. Tanner lectures on human values, University of Michigan.
  7. Doyle, J. (1983) What is ra:\ional psychology? Toward a modern mental philosophy. AI Magazine 4 (3), 50-53.
  8. Etzioni. Tractable decision-analytic control. Proc. of 1st International Conference on Knowledge Representa- tion and Reasoning, 114-125, 1989.
  9. 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.
  10. 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.
  11. Horvitz, E. J. (1988) Reasoning about beliefs and actions under computational resource constraints. In
  12. Levitt, T., Lemmer, J., and. Kanal, L. (Eds.) Uncertainty in Artificial Intelligence 9. Amsterdam: North Holland.
  13. 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.
  14. 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.
  15. 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.
  16. Newell, A. {1981) The knowledge level. AI Magazine 2, 1-20.
  17. Nilsson, N. J. (1991} Logic and artificial intelligence. Artificial Intelligence 45, 31-56.
  18. Russell, S. J., and Subramanian, D. (1992) On provably rational agents with limited performance hardware. In
  19. Baum, E. (Ed.) Computational learning and cognition: Proceeding' of the Third NEG Sympo.sium, SIAM Press.
  20. RuSIIdJ., S. J., and Wefald, E. H. {1989) Principles of metareasoning. In Proc. KR-89.
  21. Rusaell, S. J., and Wefald, E. H. {1991) Do the right th;ng: StudieJJ in limited rationality. Cambridge, MA: MIT Press.
  22. Russell, S. J., aDd Zilberstein, S {1991) Composing real- time systems. ID Proc. JJCAI-91, Sydney.
  23. 21}' Sav~e, L. J. (1972) The foundation.s of .statiJJtic.s, 2nd rev . ed. New York: Dover.
  24. Simon, H. A. (1976) On how to decide what to do. In [23}.
  25. Simon, H. A. (1982) Model.s of bounded rationalit11, Vol- ume 2. Cambridge: MIT Pre88.
  26. 24} Valiant, L. G. {1984) A tla.eory of the learnable. Com- munication.s of the A CM 18(11 }, 1134-42.
  27. 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.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards