Distributed Thompson sampling under constrained communication
This work addresses the challenge of efficient optimization in distributed systems with limited communication, offering incremental improvements for scenarios like sensor networks or collaborative robotics.
The paper tackles the problem of multi-agent Bayesian optimization under constrained communication by applying distributed Thompson sampling with Gaussian processes, achieving theoretical bounds on regret that depend on the communication graph structure and demonstrating faster convergence than sequential single-agent methods when the graph is connected.
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.