Anytime algorithms for multi-armed bandit problems

ABSTRACT

How should a decision-maker perform repeated choices so as to optimize the average cost or benefit of those choices in the long run? This question motivates the theory of online learning, which encompasses problems such as the well-known best-expert [13, 9] and multi-armed bandit [10, 1] problems. This paper concerns a new approach to dealing with multi-armed bandit problems in which the decision-maker's strategy set is large (exponential or possibly infinite). Recent theoretical progress on the analysis of algorithms for such problems (e.g. [2, 3, 8, 11, 14]) has led to improved online algorithms for problems in areas such as online routing [2], dynamic pricing mechanisms [4, 5, 12], and analysis of reputation systems in e-commerce and peer-to-peer networks [3].

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: Baruch Awerbuch , Robert D. Kleinberg, Adaptive routing with end-to-end feedback: distributed learning and geometric approaches, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007367]
• 3: B. Awerbuch and R. Kleinberg, Competitive collaborative learning, in Proceedings of the 18th Annual Conference on Learning Theory (COLT), 2005. To appear.
• 4: Avrim Blum , Jason D. Hartline, Near-optimal online auctions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 5: Avrim Blum , Vijay Kumar , Atri Rudra , Felix Wu, Online learning in online auctions, Theoretical Computer Science, v.324 n.2-3, p.137-146, 20 September 2004 [doi>10.1016/j.tcs.2004.05.012]
• 6: M. Boddy, Anytime problem solving using dynamic programming, Proceedings of National Conference on Artificial Intelligence (AAAI), (1991).
• 7: E. Cope, Regret and convergence bounds for immediate-reward reinforcement learning with continuous action spaces, 2004. Unpublished manuscript.
• 8: Abraham D. Flaxman , Adam Tauman Kalai , H. Brendan McMahan, Online convex optimization in the bandit setting: gradient descent without a gradient, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 10: J. C. Gittins and D. M. Jones, A dynamic allocation index for the sequential design of experiments, in Progress in Statistics, J. G. et al., ed., North-Holland, 1974, pp. 241--266.
• 11: R. Kleinberg, Nearly tight bounds for the continuum-armed bandit problem, in Advances in Neural Information Processing Systems 17, L. K. Saul, Y. Weiss, and L. Bottou, eds., MIT Press, Cambridge, MA, 2005, pp. 697--704.
• 12: Robert Kleinberg , Tom Leighton, The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.594, October 11-14, 2003
• 13: 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]
• 14: H. B. McMahan and A. Blum, Online geometric optimization in the bandit setting against an adaptive adversary, in Proceedings of the 17th Annual Conference on Learning Theory (COLT), vol. 3120 of Lecture Notes in Computer Science, Springer Verlag, 2004, pp. 109--123.
• 15: S. Zilberstein, Operational rationality through compilation of anytime algorithms, 1993.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory