Multi-armed bandits in metric spaces

Robert Kleinberg, Aleksandrs Slivkins, Eli Upfal

Abstract

Standard multi-armed bandit (MAB) problems typically focus on a finite set of discrete choices. However, many modern applications involve massive or infinite strategy sets, such as continuous parameter tuning or large-scale targeted advertising. This paper generalizes the MAB framework to infinite strategy sets that form a metric space, where the payoff function is Lipschitz continuous. We introduce the "zooming algorithm," an adaptive approach that focuses exploration on promising regions of the metric space. By leveraging the intrinsic dimensionality of the space and the payoff function, the algorithm achieves near-optimal regret bounds that adapt to the difficulty of the specific problem instance.

Introduction

In a multi-armed bandit problem, an agent must choose from a set of strategies (arms) over a series of trials to maximize total payoff. This requires balancing the exploration of unknown arms with the exploitation of known high-performing ones. While this problem is well-understood for small, finite arm sets, it becomes intractable for infinite sets without further assumptions. To address this, we assume that strategies reside in a metric space, allowing us to measure the distance or similarity between any two choices. Furthermore, we assume the payoff function is Lipschitz continuous, meaning that strategies close to one another yield similar expected rewards.

This spatial structure allows for the design of algorithms that can generalize information from one strategy to its neighbors, making the search for an optimal strategy possible even in an infinite "haystack."

The Zooming Algorithm

Rather than relying on a static discretization of the metric space—which often leads to inefficient exploration—the authors propose the Zooming Algorithm. This method employs an adaptive refinement strategy characterized by three main components:

  1. Adaptive Refinement: The algorithm maintains a set of "active" strategies. Instead of a fixed grid, it dynamically activates new strategies based on observed performance.
  2. Confidence Radii: Each active strategy is assigned a confidence radius that shrinks as the strategy is played more frequently. This radius represents the uncertainty of the payoff estimate in that region.
  3. Zooming In: When a region shows a high upper confidence bound (indicating it is potentially optimal), the algorithm "zooms in" by activating new, denser strategies within that neighborhood. Conversely, unpromising regions are left sparsely explored, saving computational and trial resources.

To manage the complexity of infinite spaces, the algorithm utilizes a "covering oracle"—a computational black box that identifies whether a set of balls covers the entire space or provides an uncovered point for further exploration.

Theoretical Contributions: Zooming and Covering Dimensions

A central contribution of this work is the introduction of new metrics to quantify the complexity of bandit problems in metric spaces:

  • The Zooming Dimension: This instance-dependent metric measures the size of the set of near-optimal strategies. A problem with a highly peaked, isolated optimum has a low zooming dimension, while a flat, broad optimum has a high one. The zooming algorithm is self-tuning, meaning it adapts to this dimension without prior knowledge of the payoff function's shape.
  • Max-Min-Covering Dimension: To establish the fundamental limits of any algorithm, the authors introduce this topological concept. it captures the dimensionality of the most densely packed "bottleneck" subset within the metric space, representing the worst-case difficulty of the environment.

Key Results and Regret Bounds

The paper provides tight bounds on regret—the difference between the algorithm's cumulative payoff and that of the optimal strategy:

  • Instance-Dependent Performance: The zooming algorithm achieves a regret of $\tilde{O}(t^{\frac{d+1}{d+2}})$, where $t$ is the number of trials and $d$ is the zooming dimension. This demonstrates that adaptive zooming is strictly superior to static grids for "benign" payoff functions.
  • Worst-Case Optimality: For any compact metric space with a max-min-covering dimension of $d$, the authors prove a lower bound of $\Omega(t^{\frac{d+1}{d+2}})$. They also provide a specialized (though mathematically complex) algorithm that matches this lower bound for any metric space.
  • Target MAB: In scenarios where the reward is based on the distance to a hidden target set, the zooming algorithm achieves exceptionally low poly-logarithmic regret (e.g., $\tilde{O}(\log^2 t)$).

Limitations and Conclusion

While theoretically robust, the "per-metric optimal" algorithm relies on complex oracles, such as transfinite depth oracles, which may be difficult to implement in practice. Additionally, the current topological definitions of dimensionality are specifically tailored for infinite spaces; extending these concepts to massive but finite metric spaces remains a subject for future research. Despite these challenges, the zooming algorithm provides a powerful, self-tuning framework for optimization in complex, continuous environments.

Summary updated

BibTeX
@inproceedings{kleinberg2008multi,
  author = {Robert Kleinberg and Aleksandrs Slivkins and Eli Upfal},
  title = {{Multi-armed bandits in metric spaces}},
  booktitle = {STOC},
  year = {2008},
  url = {https://openreview.net/forum?id=fl2mHk8q3oX},
}
Figure