Multi-Armed Bandits in Metric Spaces
  In a multi-armed bandit problem, an online algorithm chooses from a set of
strategies in a sequence of trials so as to maximize the total payoff of the
chosen strategies. While the performance of bandit algorithms with a small
finite strategy set is quite well understood, bandit problems with large
strategy sets are still a topic of very active investigation, motivated by
practical applications such as online auctions and web advertisement. The goal
of such research is to identify broad and natural classes of strategy sets and
payoff functions which enable the design of efficient solutions. In this work
we study a very general setting for the multi-armed bandit problem in which the
strategies form a metric space, and the payoff function satisfies a Lipschitz
condition with respect to the metric. We refer to this problem as the
"Lipschitz MAB problem". We present a complete solution for the multi-armed
problem in this setting. That is, for every metric space (L,X) we define an
isometry invariant which bounds from below the performance of Lipschitz MAB
algorithms for X, and we present an algorithm which comes arbitrarily close to
meeting this bound. Furthermore, our technique gives even better results for
benign payoff functions.
