Sharp Dichotomies for Regret Minimization in Metric Spaces

Robert D. Kleinberg, Aleksandrs Slivkins

TL;DR

This paper reveals a "gap" in the difficulty of online learning: in metric spaces, the optimal regret for Lipschitz bandits and experts is either very small ($O(\log t)$) or significantly larger ($\Omega(\sqrt{t})$), with no middle ground. Surprisingly, this jump doesn't happen at the transition from finite to infinite spaces, but rather depends on whether the space's completion is compact and countable.

What Problem Does This Paper Address?

In the classic Multi-Armed Bandit (MAB) problem, an agent chooses between $k$ actions and tries to minimize "regret"—the difference between the reward they got and the reward they could have gotten by picking the single best action in hindsight. For a finite number of actions, we've known since the 80s that regret grows logarithmically ($O(\log t)$). However, when actions are chosen from a continuous space (like the unit interval $[0, 1]$), regret typically grows as a power of time (at least $\Omega(\sqrt{t})$).

The authors ask: Is there anything in between? Specifically, they look at Lipschitz MAB, where actions live in a metric space and similar actions are guaranteed to have similar rewards. They seek to characterize exactly which metric spaces allow for "easy" learning (logarithmic regret) and which are "hard" (square-root regret or worse).

Methods

The paper bridges the gap between online learning theory and point-set topology.

  1. Algorithmic Upper Bounds: The authors develop algorithms based on "well-ordering" the metric space. For spaces that are "well-orderable" (a topological property), they show they can achieve regret arbitrarily close to logarithmic by carefully managing exploration across the space.
  2. Lower Bounds via "Ball-Trees": To prove that certain spaces are inherently hard, they construct "ball-trees"—infinite binary trees of disjoint regions within the metric space. They then use information-theoretic tools (KL-divergence) to show that any algorithm will struggle to distinguish between different reward functions hidden within these regions.
  3. Topological Tools: The proofs rely heavily on the Cantor-Bendixson Theorem, which describes how sets can be decomposed into "perfect" subsets (which contain no isolated points) and countable parts.

Datasets

As a theoretical paper in computer science and mathematics, no empirical datasets were used. The "data" consists of abstract metric spaces, such as:

  • Finite metric spaces.
  • The unit interval $[0, 1]$ with standard Euclidean distance.
  • Compact, countable metric spaces (e.g., $\{0\} \cup \{1/n : n \in \mathbb{N}\}$).
  • Non-compact spaces (where the authors prove regret must be linear, i.e., $o(t)$ is impossible).

Key Insights and Ideas

  • The "Missing Middle": There is a fundamental "jump" in complexity. You can't have a metric space where the best possible regret is, say, $t^{1/4}$. It's either $\log t$ or it's at least $\sqrt{t}$.
  • Countability Matters: The boundary for "easy" learning isn't "finite vs. infinite." An infinite metric space can still yield $O(\log t)$ regret if its completion is compact and countable.
  • The Role of Compactness: If a space isn't "pre-compact" (meaning it can't be covered by a finite number of small balls), the problem becomes completely intractable—you can't even achieve sublinear regret.
  • New Dimensionality Measures: For the "full-feedback" (expert) version of the problem, standard notions like "covering dimension" are too coarse. The authors introduce Log-Covering Dimension (LCD) and MaxMinLCD to precisely characterize regret in uncountable spaces.

Key Results

  • Theorem 1.2 (The MAB Dichotomy): For any metric space, Lipschitz MAB regret is either $O(\text{polylog } t)$ or $\Omega(\sqrt{t})$. The "easy" case occurs if and only if the completion of the space is compact and countable.
  • Theorem 1.4 (The Experts Dichotomy): A similar dichotomy exists for the full-feedback (best-expert) setting.
  • Theorem 1.5 (Intractability): Regret is $o(t)$ (meaning you eventually learn something) if and only if the completion of the metric space is compact.
  • Regret in Uncountable Spaces: For uncountable spaces, they show regret for the experts problem is $\Theta(t^\gamma)$, where the exponent $\gamma$ is determined by the new dimensionality notions they introduced.

Limitations and Future Work

  • Stochastic Assumption: The primary results assume rewards are stochastic (i.e., drawn from a fixed distribution over time). While they touch on the adversarial case, the sharp dichotomies are most clearly defined in the stochastic setting.
  • Knowledge of the Metric: The algorithms generally assume the learner knows the metric space and its properties (like the well-ordering) upfront.
  • Oracle Access: The authors note that their "easy" algorithms require access to specific topological oracles (like a covering oracle or an ordering oracle), which might be computationally expensive to implement for complex spaces.
  • Future Direction: A natural extension would be investigating whether similar dichotomies exist in other structured bandit problems, such as those with convex or linear payoffs in high-dimensional spaces.

Summary updated

BibTeX
@inproceedings{kleinberg2009sharp,
  author = {Robert D. Kleinberg and Aleksandrs Slivkins},
  title = {{Sharp Dichotomies for Regret Minimization in Metric Spaces}},
  booktitle = {SODA},
  year = {2009},
  doi = {10.1137/1.9781611973075.68},
}
Figure