Robbing the bandit: less regret in online geometric optimization against an adaptive adversary

ABSTRACT

We consider "online bandit geometric optimization," a problem of iterated decision making in a largely unknown and constantly changing environment. The goal is to minimize "regret," defined as the difference between the actual loss of an online decision-making procedure and that of the best single decision in hindsight. "Geometric optimization" refers to a generalization of the well-known multi-armed bandit problem, in which the decision space is some bounded subset of R^d, the adversary is restricted to linear loss functions, and regret bounds should depend on the dimensionality d, rather than the total number of possible decisions. "Bandit" refers to the setting in which the algorithm is only told its loss on each round, rather than the entire loss function.McMahan and Blum [10] presented the best known algorithm in this setting, and proved that its expected additive regret is O(poly(d)T^3/4). We simplify and improve their analysis of this algorithm to obtain regret O(poly(d)T^2/3).We also prove that, for a large class of full-information online optimization problems, the optimal regret against an adaptive adversary is the same as against a non-adaptive adversary.

REFERENCES

• 1: P. Auer , N. Cesa-Bianchi , Y. Freund , R. E. Schapire, Gambling in a rigged casino: The adversarial multi-armed bandit problem, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.322, October 23-25, 1995
• 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: V. Dani and T. P. Hayes. Beating the adversarial multiarmed bandit through improved hedging. (working title) Manuscript, 2005.
• 5: 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]
• 6: J. Hannan. Approximation to Bayes risk in repeated play. In: Contributions to the Theory of Games, vol III, 97--139, M. Dresher, A. W. Tucker and P. Wolfe, editors, Princeton University Press (1957).
• 7: T. Hayes. An Azuma-Hoeffding inequality for vector-valued martingales. Manuscript (2003).
• 8: A. Kalai and S. Vempala. Efficient algorithms for online optimization. In: Proceedings of the 16th annual Conference on Learning Theory (2003).
• 9: 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]
• 10: 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 (2004) 109--123.
• 11: H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society. 55 (1952) 527--535.
• 12: M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the 20th International Conference on Machine Learning (2003).

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Geometrical problems and computations

General Terms:
Algorithms, Theory