Better algorithms for benign bandits

ABSTRACT

The online multi-armed bandit problem and its generalizations are repeated decision making problems, where the goal is to select one of several possible decisions in every round, and incur a cost associated with the decision, in such a way that the total cost incurred over all iterations is close to the cost of the best fixed decision in hindsight. The difference in these costs is known as the regret of the algorithm. The term bandit refers to the setting where one only obtains the cost of the decision used in a given iteration and no other information.

Perhaps the most general form of this problem is the non-stochastic bandit linear optimization problem, where the set of decisions is a convex set in some Euclidean space, and the cost functions are linear. Only recently an efficient algorithm attaining Õ (√T) regret was discovered in this setting.

In this paper we propose a new algorithm for the bandit linear optimization problem which obtains a regret bound of Õ (√Q), where Q is the total variation in the cost functions. This regret bound, previously conjectured to hold in the full information case, shows that it is possible to incur much less regret in a slowly changing environment even in the bandit setting. Our algorithm is efficient and applies several new ideas to bandit optimization such as reservoir sampling.

REFERENCES

• 1: J. Abernethy, E. Hazan, and A. Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In COLT, 2008.
• 2: 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]
• 3: 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]
• 4: Aharon Ben-Tal , Arkadiaei Semenovich Nemirovskiaei, Lectures on modern convex optimization: analysis, algorithms, and engineering applications, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 5: Nicolò Cesa-Bianchi , Yishay Mansour , Gilles Stoltz, Improved second-order bounds for prediction with expert advice, Machine Learning, v.66 n.2-3, p.321-352, March 2007 [doi>10.1007/s10994-006-5001-7]
• 6: Nicolo Cesa-Bianchi , Gabor Lugosi, Prediction, Learning, and Games, Cambridge University Press, New York, NY, 2006
• 7: V. Dani, T. Hayes, and S. Kakade. The price of bandit information for online optimization. In NIPS, 2008.
• 8: Varsha Dani , Thomas P. Hayes, Robbing the bandit: less regret in online geometric optimization against an adaptive adversary, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.937-943, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109660]
• 9: 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
• 10: J. Hannan. Approximation to bayes risk in repeated play. In M. Dresher, A. W. Tucker, and P. Wolfe, editors, Contributions to the Theory of Games, volume III, pages 97--139, 1957.
• 11: E. Hazan and S. Kale. Extracting certainty from uncertainty: Regret bounded by variation in costs. In COLT, 2008.
• 12: E. Hazan and S. Kale. How to invest in calmer markets (without compromising universality). Manuscript, 2008.
• 13: T L Lai, Asymptotically efficient adaptive control in Stochastic regression models, Advances in Applied Mathematics, v.7 n.1, p.23-45, March 1986 [doi>10.1016/0196-8858(86)90004-7]
• 14: H. B. McMahan and A. Blum. Online geometric optimization in the bandit setting against an adaptive adversary. In COLT, pages 109--123, 2004.
• 15: A. S. Nemirovskii. Interior point polynomial time methods in convex programming, 2004. Lecture Notes.
• 16: Y. E. Nesterov and A. S. Nemirovskii. Interior Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, 1994.
• 17: H. Robbins. Some aspects of the sequential design of experiments. Bull. Amer. Math. Soc., 58(5):527--535, 1952.
• 18: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms