Distributed Thompson Sampling Under Constrained Communication

Saba Zerefa, Zhaolin Ren, Haitong Ma, Na Li

TL;DR

This paper introduces a distributed Thompson sampling algorithm for Bayesian optimization, enabling multiple agents to collaboratively optimize a black-box function even when communication is limited. The authors provide theoretical guarantees on the algorithm's performance, showing that its regret depends on the connectivity of the communication network, and demonstrate its effectiveness through simulations.

What Problem Does This Paper Address?

Bayesian optimization (BO) is a powerful technique for optimizing expensive, noisy black-box functions, often used in machine learning for hyperparameter tuning and experimental design. While BO typically relies on a single agent, real-world scenarios often involve multiple agents that could potentially speed up the optimization process. Existing multi-agent BO methods often assume a centralized coordinator or fully connected communication, which is not always practical. This paper addresses the challenge of distributed Bayesian optimization where agents operate independently, can only communicate with their neighbors, and the communication network might be constrained. The goal is to achieve efficient optimization in such decentralized and potentially sparse communication settings.

Methods

The core contribution is a Distributed Thompson Sampling (DTS) algorithm. In this approach:

  • Individual GPs: Each of the $M$ agents maintains its own Gaussian Process (GP) to model the objective function. This is necessary because agents only have access to their own data and data from their neighbors.
  • Thompson Sampling for Acquisition: At each time step, each agent uses its local GP to sample a realization of the objective function and then selects the next query point by maximizing this sampled function. This balances exploration and exploitation.
  • Neighbor Communication: After querying the objective function, each agent shares its sampled point and the corresponding function value with its direct neighbors in the communication network.
  • Data Aggregation: Agents update their local GP models using their own data and the data received from their neighbors.
  • Theoretical Guarantees: The authors derive theoretical bounds on the Bayesian average regret and Bayesian simple regret. These bounds are shown to depend on the structure of the communication graph, specifically its clique cover number and clique number, indicating that higher connectivity leads to faster convergence.

Datasets

Not discussed in the paper. The paper uses standard optimization test functions for evaluation.

Key Insights and Ideas

  • Decentralization is Feasible: The paper demonstrates that distributed Bayesian optimization is possible and can be theoretically analyzed even without a central coordinator.
  • Communication Structure Matters: The regret bounds are directly influenced by the connectivity of the communication graph. Densely connected graphs lead to better performance, which is intuitive as agents can share information more broadly.
  • Thompson Sampling Adapts: Using Thompson sampling in a distributed setting allows agents to adapt their exploration-exploitation strategy based on their local information, contributing to efficient optimization.
  • Theoretical Advantage over Sequential: The derived bounds suggest that for connected communication graphs, the distributed approach can achieve faster convergence than a single-agent sequential approach in the same number of rounds.

Key Results

  • Regret Bounds: The paper establishes theoretical bounds for Bayesian average regret and Bayesian simple regret. For average regret, the bound is shown to be dependent on the clique cover number of the communication graph, suggesting that a graph decomposable into fewer, larger complete subgraphs leads to lower regret. For simple regret, the bound depends on the size of the largest complete subgraph, indicating that a larger clique improves performance.
  • Connectivity Impact: The theoretical results imply that higher connectivity in the communication graph leads to better regret convergence rates.
  • Numerical Validation: Simulations on the Rosenbrock and Ackley functions with Erdős-Rényi random graphs show that graphs with higher connectivity probabilities (0.4 and 0.6) achieve lower regret compared to sparser graphs (0.2), supporting the theoretical findings.

Limitations and Future Work

  • Synchronous Assumption: The current algorithm assumes a synchronous global clock, meaning all agents update and query at the same time steps.
  • Tighter Regret Bounds: The authors suggest developing tighter regret bounds.
  • Asynchronous and Heterogeneous Settings: Future work could explore asynchronous updates and scenarios where agents have different computational capabilities or access to different types of information.
  • Scalability: While distributed, the current analysis might not fully capture the scalability challenges in very large networks.
  • Kernel Choice: The theoretical analysis relies on specific kernel properties, and extending it to more general kernels could be beneficial.

Summary updated

Abstract

In Bayesian optimization, a black-box function is maximized via the use of a surrogate model. We apply distributed Thompson sampling, using a Gaussian process as a surrogate model, to approach the multi-agent Bayesian optimization problem. In our distributed Thompson sampling implementation, each agent receives sampled points from neighbors, where the communication network is encoded in a graph; each agent utilizes their own Gaussian process to model the objective function. We demonstrate theoretical bounds on Bayesian average regret and Bayesian simple regret, where the bound depends on the structure of the communication graph. Unlike in batch Bayesian optimization, this bound is applicable in cases where the communication graph amongst agents is constrained. When compared to sequential single-agent Thompson sampling, our bound guarantees faster convergence with respect to time as long as the communication graph is connected. We confirm the efficacy of our algorithm with numerical simulations on traditional optimization test functions, demonstrating the significance of graph connectivity on improving regret convergence.
BibTeX
@article{zerefa2024distributed,
  author = {Saba Zerefa and Zhaolin Ren and Haitong Ma and Na Li},
  title = {{Distributed Thompson Sampling Under Constrained Communication}},
  journal = {IEEE Control. Syst. Lett},
  year = {2024},
  doi = {10.1109/lcsys.2024.3525096},
}
Figure