The Lipschitz multi-armed bandit (MAB) problem generalizes the classical
multi-armed bandit problem by assuming one is given side information consisting
of a priori upper bounds on the difference in expected payoff between certain
pairs of strategies. Classical results of Lai and Robbins (1985) and Auer et al.
(2002) imply a logarithmic regret bound for the Lipschitz MAB problem on finite
metric spaces. Recent results on continuum-armed bandit problems and their
generalizations imply lower bounds of *√t*, or stronger, for many
infinite metric spaces such as the unit interval. Is this dichotomy universal?
We prove that the answer is yes: for every metric space, the optimal regret of a
Lipschitz MAB algorithm is either bounded above by any *f∈ ω(log
t)*, or bounded below by any *g∈ o(√t)*. Perhaps surprisingly,
this dichotomy does not coincide with the distinction between finite and infinite
metric spaces; instead it depends on whether the completion of the metric space
is compact and countable. Our proof connects upper and lower bound techniques in
online learning with classical topological notions such as perfect sets and the
Cantor-Bendixson theorem.

We also consider the "full-feedback" (a.k.a., "best-expert") version of
Lipschitz MAB problem, termed the "Lipschitz experts problem", and show that this
problem exhibits a similar dichotomy. We proceed to give nearly matching upper
and lower bounds on regret in the Lipschitz experts problem on uncountable metric
spaces. These bounds are of the form *˜Θ(t^γ)*, where the
exponent *γ∈ [1/2, 1]* depends on the metric space. To
characterize this dependence, we introduce a novel dimensionality notion tailored
to the experts problem. Finally, we show that both Lipschitz bandits and
Lipschitz experts problems become completely intractable (in the sense that no
algorithm has regret *o(t)*) if and only if the completion of the metric
space is non-compact.