A Parallel algorithm for $\mathcal{X}$-Armed bandits

Cheng Chen, Shuang Liu, Zhihua Zhang, Wu-Jun LiarXiv 2015 · OpenReview

Abstract

The $\mathcal{X}$-armed bandit problem focuses on finding the global maximum of an unknown stochastic function $f$ within a finite budget of $n$ evaluations. As modern applications increasingly involve large-scale datasets and complex search spaces, the need for efficient parallelization has become paramount. We present a novel anytime distributed $\mathcal{X}$-armed bandit algorithm where $m$ players collaborate to optimize the search. By employing a level-order tree traversal strategy, our approach achieves a theoretical speedup factor of $m$ compared to classical serial algorithms, while maintaining a communication overhead that scales only logarithmically with the total budget. Numerical results demonstrate that our method effectively utilizes multiple players to minimize loss, making it a robust solution for distributed optimization.

Introduction

The $\mathcal{X}$-armed bandit problem involves identifying the maximum of a "black-box" function $f$ over a continuous or measurable space $\mathcal{X}$. Unlike traditional multi-armed bandits that choose from a finite set of arms, the search space here is infinite. Evaluations are typically expensive and subject to noise, requiring algorithms to be highly efficient with a limited sampling budget $n$.

In the era of big data, a single machine often lacks the computational bandwidth to perform sufficient evaluations within a reasonable timeframe. However, standard $\mathcal{X}$-bandit algorithms, such as Hierarchical Optimistic Optimization (HOO) or Stochastic Simultaneous Optimistic Optimization (StoSOO), are notoriously difficult to parallelize. These algorithms typically traverse a hierarchical partition of the search space (a "covering tree") in a way that requires immediate feedback to determine the next evaluation point. Without constant synchronization, independent players risk redundant exploration of suboptimal regions. This paper introduces a distributed framework that maximizes speedup while minimizing the communication cost between machines.

Methodology

Level-Order Traversal Strategy

Traditional serial algorithms often dive deep into promising branches of the covering tree immediately. In contrast, our proposed algorithm utilizes a level-order traversal (breadth-first) strategy. This shift is fundamental to enabling efficient parallelization.

Parallel Sampling and Synchronization

At each depth $h$ of the hierarchical tree, the algorithm identifies a "confidence set" $S_h$ containing nodes that are potentially optimal. The $m$ players evaluate these nodes in parallel. Communication is synchronized: players only exchange information after completing all samples at the current depth. By broadcasting mean rewards, the group calculates a highly accurate aggregate estimate ($\hat{\mu}_{h,i}$) for every node at that level.

Optimistic Expansion

A node is expanded to the next level of the tree only if its aggregate estimate is sufficiently close to the maximum estimate found at that depth. Specifically, a node $i$ is expanded if: $$\hat{\mu}_{h,i} \geq \hat{\mu}^*_h - 3\nu_1\rho^h$$ This ensures the algorithm remains "optimistic" in the face of uncertainty, preventing the premature exclusion of the global peak. Furthermore, the algorithm is "anytime," meaning it does not require prior knowledge of the total budget $n$ and can return the best estimate found at any point of interruption.

Theoretical Analysis

Speedup and Regret

Our theoretical analysis shows that the distributed algorithm is $m$ times faster than the classical single-player counterpart. The simple regret (the distance from the true maximum) is bounded by: $$O((mn)^{-1/(d+2)}(\log n)^{1/(d+2)})$$ where $d$ is the near-optimality dimension. Compared to the serial bound of $O(n^{-1/(d+2)}(\log n)^{1/(d+2)})$, the distributed version effectively treats the budget as $m \times n$.

Communication Efficiency

A critical feature of this algorithm is its low communication overhead. The number of communication rounds is only $O(\log(mn))$. Even in scenarios involving millions of evaluations, players only need to synchronize a few dozen times. The total number of values any single player must broadcast is bounded by $M \leq O([\frac{mn}{\log n}]^{d/(d+2)})$.

Empirical Evaluation

Experimental Setup

The algorithm was tested using two synthetic benchmark functions under truncated Gaussian noise $\mathcal{N}(0, 1)$:

  1. Sine-based Function: $f(x) = \frac{1}{2}(\sin(13x) \sin(27x)/2 + 1)$, representing a relatively smooth structure with local optima.
  2. Garland Function: $f(x) = x(1 - x)(4 - \sqrt{|\sin(60x)|})$, a "needle-in-a-haystack" problem with many sharp local optima.

Results

Experiments conducted with 1, 4, and 16 players confirmed the theoretical speedup. In the 16-player configuration, the algorithm reached lower loss levels significantly faster than the single-player version. For the difficult Garland function, the 16-player setup achieved a level of accuracy in 100 steps that the single-player setup could not match even after 1,000 steps.

Conclusion and Future Work

This paper provides a scalable and communication-efficient framework for distributed $\mathcal{X}$-armed bandits. By forcing synchronization at the level-order transition, we prevent uncoordinated traversal and achieve near-linear speedup.

Future research will address current limitations, such as the requirement for prior knowledge of smoothness parameters ($\nu_1$ and $\rho$). Developing a version that estimates these parameters online would increase the algorithm's robustness in true black-box scenarios. Additionally, while this work focuses on simple regret, extending the distributed framework to optimize cumulative regret remains a significant challenge for the field.

Summary updated

Abstract

The target of $\mathcal{X}$-armed bandit problem is to find the global maximum of an unknown stochastic function $f$, given a finite budget of $n$ evaluations. Recently, $\mathcal{X}$-armed bandits have been widely used in many situations. Many of these applications need to deal with large-scale data sets. To deal with these large-scale data sets, we study a distributed setting of $\mathcal{X}$-armed bandits, where $m$ players collaborate to find the maximum of the unknown function. We develop a novel anytime distributed $\mathcal{X}$-armed bandit algorithm. Compared with prior work on $\mathcal{X}$-armed bandits, our algorithm uses a quite different searching strategy so as to fit distributed learning scenarios. Our theoretical analysis shows that our distributed algorithm is $m$ times faster than the classical single-player algorithm. Moreover, the number of communication rounds of our algorithm is only logarithmic in $mn$. The numerical results show that our method can make effective use of every players to minimize the loss. Thus, our distributed approach is attractive and useful.
BibTeX
@misc{chen2015parallel,
  author = {Cheng Chen and Shuang Liu and Zhihua Zhang and Wu-Jun Li},
  title = {{A Parallel algorithm for $\textbackslash\{\}mathcal\{X\}$-Armed bandits}},
  year = {2015},
  eprint = {1510.07471},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1510.07471},
}
Figure