Combining expert advice in reactive environments

ABSTRACT

“Experts algorithms” constitute a methodology for choosing actions repeatedly, when the rewards depend both on the choice of action and on the unknown current state of the environment. An experts algorithm has access to a set of strategies (“experts”), each of which may recommend which action to choose. The algorithm learns how to combine the recommendations of individual experts so that, in the long run, for any fixed sequence of states of the environment, it does as well as the best expert would have done relative to the same sequence. This methodology may not be suitable for situations where the evolution of states of the environment depends on past chosen actions, as is usually the case, for example, in a repeated non-zero-sum game.A general exploration-exploitation experts method is presented along with a proper definition of value. The definition is shown to be adequate in that it both captures the impact of an expert's actions on the environment and is learnable. The new experts method is quite different from previously proposed experts algorithms. It represents a shift from the paradigms of regret minimization and myopic optimization to consideration of the long-term effect of a player's actions on the environment. The importance of this shift is demonstrated by the fact that this algorithm is capable of inducing cooperation in the repeated Prisoner's Dilemma game, whereas previous experts algorithms converge to the suboptimal non-cooperative play. The method is shown to asymptotically perform as well as the best available expert. Several variants are analyzed from the viewpoint of the exploration-exploitation tradeoff, including explore-then-exploit, polynomially vanishing exploration, constant-frequency exploration, and constant-size exploration phases. Complexity and performance bounds are proven.

REFERENCES

• 1: Peter Auer , Nicolò Cesa-Bianchi , Yoav Freund , Robert E. Schapire, The Nonstochastic Multiarmed Bandit Problem, SIAM Journal on Computing, v.32 n.1, p.48-77, 2003 [doi>10.1137/S0097539701398375]
• 2: Nicolò Cesa-Bianchi , Yoav Freund , David Haussler , David P. Helmbold , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Journal of the ACM (JACM), v.44 n.3, p.427-485, May 1997 [doi>10.1145/258128.258179]
• 3: Chernoff, H. 1952. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493--507.
• 4: de Farias, D., and Megiddo, N. 2004. How to combine expert (or novice) advice when actions impact the environment. In Advances in Neural Information Processing Systems, Vol. 16.
• 5: Feller, W. 1971. Probability Theory and its Applications. Wiley, New York.
• 6: Dean P. Foster , Rakesh V. Vohra, A randomization rule for selecting forecasts, Operations Research, v.41 n.4, p.704-709, July–Aug. 1993 [doi>10.1287/opre.41.4.704]
• 7: Foster, D. and Vohra, R. 1999. Regret and the on-line decision problem. Games Econ. Behav. 29, 7--35.
• 8: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Proceedings of the Second European Conference on Computational Learning Theory, p.23-37, March 13-15, 1995
• 9: Freund, Y., and Schapire, R. E. 1999. Adaptive game playing using multiplicative weights. Games Econ. Behav. 29, 79--103.
• 10: Fudenberg, D., and Levine, D. 1997. The Theory of Learning in Games. The MIT Press, Cambridge, MA.
• 11: Hoeffding, W. 1963. Probability inequalities for sums of bounded random variables. J. ASA 58, 13--30.
• 12: Kakade, S. 2003. On the sample complexity of reinforcement learning. Ph.D. dissertation, Gatsby Computational Neuroscience Unit, University College, London, England.
• 13: Michael Kearns , Satinder Singh, Finite-sample convergence rates for Q-learning and indirect algorithms, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.996-1002, July 1999
• 14: Michael Kearns , Satinder Singh, Near-Optimal Reinforcement Learning in Polynomial Time, Machine Learning, v.49 n.2-3, p.209-232, November-December 2002 [doi>10.1023/A:1017984413808]
• 15: Lai, T.-L., and Yakowitz, S. 1995. Machine learning and nonparametric bandit theory. IEEE Trans. Automat. Cont. 40, 7, 1199--1209.
• 16: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 17: V. Vovk, A game of prediction with expert advice, Journal of Computer and System Sciences, v.56 n.2, p.153-173, April 1998 [doi>10.1006/jcss.1997.1556]
• 18: 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]
• 19: Williams, D. 1991. Probability with Martingales. Cambridge University Press, Cambridge, UK.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms

Keywords:
Sequential decision making, complexity and performance bounds, experts algorithms, exploration-exploitation tradeoffs, reactive environments