Approximate methods for sequential decision making using expert advice

ABSTRACT

We consider a game theoretic approach for sequentially choosing decisions by combining the suggestions of a fixed number of experts. Since the optimal decision making strategy is often computationally expensive, we present a methodology for obtaining approximate strategies with provably good performance. These methods are applicable to any decision problem with bounded payoff function, are computationally feasible, and arise naturally as approximations to the exact solution. We illustrate the ideas by applying our results to the problem of predicting a sequence of letters drawn from a finite alphabet with the goal being to minimize the number of mistakes made.

REFERENCES

• 1: Nicolò Cesa-Bianchi , Yoav Freund , David P. Helmbold , David Haussler , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.382-391, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167198]
• 2: T. H. Chung. Sequential decision making using expert advice. To appear in the 1994 proceedings of the International Symposium on Information Theory.
• 3: Thomas H. Chung, Minimax learning in iterated games via distributional majorization, Stanford University, Stanford, CA, 1994
• 4: T. M. Cover. Behavior of sequential predictors of binary sequences. In Proceedings of the ~th Prague Conference on Information Theory, Statistical Decision Functions and Random Processes, pages 263- 272, 1965.
• 5: J. Galambos. The Asymptotic Theory of Extreme Order Statistics. R. E. Kreiger, second edition, 1987.
• 6: A. J. Jones. Game Theory, Mathematical Models of Conflict. Ellis Horwood Limited, Chichester, England, 1980.
• 7: 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

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory