An optimal-control application of two paradigms of on-line learning

ABSTRACT

We describe and compare two paradigms of on-line learning, which we call Bayesian and Popperian. In this paper the Bayesian paradigm is represented by Littlestone and Warmuth's Weighted Majority Algorithm, and the Popperian paradigm is represented by Rivest and Schapire's reset-free algorithm for exact learning of finite automata with membership and equivalence queries. Both algorithms are applied to the problem of optimal control of a finite-state plant in a finite-state environment. The advantage of the control strategy based on the Weighted Majority Algorithm is its robustness and better performance (actually, its performance is nearly optimal in the class of deterministic control strategies), and the advantage of the control strategy based on Rivest and Schapire's algorithm is its computational efficiency.

REFERENCES

• 1: D. Angluin. A note on the number of queries needed to identify regular languages. Inform. Control 51, 76-87 (1981).
• 2: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• 3: G.E.P. Box. Comment on "The unity and diversity of probability' by G.Shafer. Statist. Sci. 5,448-449 (1990).
• 4: A.P. Dawid. Statistical theory: the prequential approach (with discussion). J. R. Statist. Soc. A 147, 278-292 (1984).
• 5: E.M. Gold. Language identification in the limit. Inform. Control 10,447-474 (1967).
• 6: E.M. Gold. System identification via state characterization. Automatica 8,621-636 (1972).
• 7: David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
• 8: Nick Littlestone , Manfred K. Warmuth, THE WEIGHTED MAJORITY ALGORITHM (Supersedes 89-16), University of California at Santa Cruz, Santa Cruz, CA, 1992
• 9: D.A. Martin. Borel determinacy. Ann. Math. 102, 363-371 (1975).
• 10: Ronald L. Rivest , Robert E. Schapire, Inference of finite automata using homing sequences, Information and Computation, v.103 n.2, p.299-347, April 1993 [doi>10.1006/inco.1993.1021]
• 11: Volodimir G. Vovk, Aggregating strategies, Proceedings of the third annual workshop on Computational learning theory, p.371-386, August 06-08, 1990, Rochester, New York, United States
• 12: V.G. Vovk. A logic of probability, with application to the foundations of statistics (with discussion). J. R. Statist. Soc. B 55, 317-351 (1993).
• 13: V.G. Vovk. On-line learning in a finite-state environment: control-theoretic approach. Technical Report V-93-1 (revised April, 1994), Independent University of Moscow, Moscow.
• 14: Christopher J. C. H. Watkins , Peter Dayan, Technical Note: $\backslash cal\; Q$-Learning, Machine Learning, v.8 n.3-4, p.279-292, May 1992 [doi>10.1007/BF00992698]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Theory, Verification