Multi-Agent Thompson Sampling for Bandit Applications with Sparse
  Neighbourhood Structures
  Multi-agent coordination is prevalent in many real-world applications.
However, such coordination is challenging due to its combinatorial nature. An
important observation in this regard is that agents in the real world often
only directly affect a limited set of neighbouring agents. Leveraging such
loose couplings among agents is key to making coordination in multi-agent
systems feasible. In this work, we focus on learning to coordinate.
Specifically, we consider the multi-agent multi-armed bandit framework, in
which fully cooperative loosely-coupled agents must learn to coordinate their
decisions to optimize a common objective. We propose multi-agent Thompson
sampling (MATS), a new Bayesian exploration-exploitation algorithm that
leverages loose couplings. We provide a regret bound that is sublinear in time
and low-order polynomial in the highest number of actions of a single agent for
sparse coordination graphs. Additionally, we empirically show that MATS
outperforms the state-of-the-art algorithm, MAUCE, on two synthetic benchmarks,
and a novel benchmark with Poisson distributions. An example of a
loosely-coupled multi-agent system is a wind farm. Coordination within the wind
farm is necessary to maximize power production. As upstream wind turbines only
affect nearby downstream turbines, we can use MATS to efficiently learn the
optimal control mechanism for the farm. To demonstrate the benefits of our
method toward applications we apply MATS to a realistic wind farm control task.
In this task, wind turbines must coordinate their alignments with respect to
the incoming wind vector in order to optimize power production. Our results
show that MATS improves significantly upon state-of-the-art coordination
methods in terms of performance, demonstrating the value of using MATS in
practical applications with sparse neighbourhood structures.
