Abstract
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.
Similar content being viewed by others
Introduction
Multi-agent coordination is prevalent in many real-world applications, such as traffic light control1, warehouse commissioning2 and wind farm control3,4. Often, such settings can be formulated as coordination problems in which agents have to cooperate in order to optimize a shared team reward5.
Handling multi-agent settings is challenging, as the size of the joint action space scales exponentially with the number of agents in the system. Therefore, an approach that directly considers all agents’ actions jointly is computationally intractable. This has made such coordination problems the central focus in the planning literature6,7,8,9. Fortunately, in real-world settings agents often only directly affect a limited set of neighbouring agents. This means that the global reward received by all agents can be decomposed into local components that only depend on small subsets of agents. Exploiting such loose couplings is key in order to keep multi-agent decision problems tractable10.
In this work, we consider learning to coordinate in multi-agent systems. For example, consider a wind farm control task, which is comprised of a set of wind turbines, and we aim to maximize the farm’s total productivity. When upstream turbines directly face the incoming wind stream, energy is extracted from wind. This reduces the productivity of downstream turbines, potentially damaging the overall power production. However, turbines have the option to rotate, in order to deflect the turbulent flow away from turbines downwind11. Due to the complex nature of the aerodynamic interactions between the turbines, constructing a model of the environment and deriving a control policy using planning techniques is extremely challenging12. Instead, a joint control policy among the turbines can be learned to effectively maximize the productivity of the wind farm13. The system is loosely coupled, as redirection only directly affects adjacent turbines.
While most of the literature only considers approximate reinforcement learning methods for learning in multi-agent systems, it has recently been shown14 that it is possible to achieve theoretical bounds on the regret (i.e., how much reward is lost due to learning). In this work, we use the multi-agent multi-armed bandit problem definition, and improve upon the state of the art. Specifically, we propose the multi-agent Thompson sampling (MATS) algorithm15, which exploits loosely-coupled interactions in multi-agent systems. The loose couplings are formalized as a coordination graph, which defines for each pair of agents whether their actions depend on each other. We assume the graph structure is known beforehand, which is the case in many real-world applications with sparse agent interactions (e.g., wind farm control).
Our method leverages the exploration-exploitation mechanism of Thompson sampling (TS). TS has been shown to be highly competitive to other popular methods, e.g., UCB16. Recently, theoretical guarantees on its regret have been established17, which renders the method increasingly popular in the literature. Additionally, due to its Bayesian nature, problem-specific priors can be specified. We argue that this has strong relevance in many practical fields, such as advertisement selection16 and influenza mitigation18,19.
We provide a finite-time Bayesian regret analysis and prove that the upper regret bound of MATS is low-order polynomial in the number of actions of a single agent for sparse coordination graphs (Corollary 1). This is a significant improvement over the exponential bound of classic TS, which is obtained when the coordination graph is ignored17. We show that MATS improves upon the state of the art in various synthetic settings. Finally, we demonstrate that MATS achieves high performance on a realistic wind farm control task, in which multiple wind turbines have to be jointly aligned to maximize the total power production.
Problem Statement
In this work, we adopt the multi-agent multi-armed bandit (MAMAB) setting14,20. A MAMAB is similar to the multi-armed bandit formalism21, but considers multiple agents factored into groups. When the agents have pulled a joint arm, each group receives a reward. The goal shared by all agents is to maximize the total sum of rewards. Formally,
Definition 1. A multi-agent multi-armed bandit (MAMAB) is a tuple \(\langle {\mathcal{D}},{\mathcal{A}},f\rangle \) where
\({\mathcal{D}}\) is the set of \(m\) enumerated agents. This set is factorized into \(\rho \), possibly overlapping, subsets of agents \({{\mathcal{D}}}^{e}\).
\({\mathcal{A}}={{\mathcal{A}}}_{1}\times \ldots \times {{\mathcal{A}}}_{m}\) is the set of joint actions, or joint arms, which is the Cartesian product of the sets of actions \({{\mathcal{A}}}_{i}\) for each of the \(m\) agents in \({\mathcal{D}}\). We denote \({{\mathcal{A}}}^{e}\) as the set of local joint actions, or local arms, for the group \({{\mathcal{D}}}^{e}\).
\(f({\boldsymbol{a}})\) is a stochastic function providing a global reward when a joint arm, \({\boldsymbol{a}}\in {\mathcal{A}}\), is pulled. The global reward function is decomposed into \(\rho \) noisy, observable and independent local reward functions, i.e., \(f({\boldsymbol{a}})={\sum }_{e\mathrm{=1}}^{\rho }{f}^{e}({{\boldsymbol{a}}}^{e})\). A local function \({f}^{e}\) only depends on the local arm \({{\boldsymbol{a}}}^{e}\) of the subset of agents in \({{\mathcal{D}}}^{e}\).
We denote the mean reward of a joint arm as \(\mu ({\boldsymbol{a}})={\sum }_{e\mathrm{=1}}^{\rho }{\mu }^{e}({{\boldsymbol{a}}}^{e})\). For simplicity, we refer to the \({i}^{{\rm{th}}}\) agent by its index \(i\).
The dependencies between the local reward functions and the agents are described as a coordination graph8.
Definition 2. A coordination graph is a bipartite graph \(G=\langle {\mathcal{D}},\{{f}^{e}{\}}_{e\mathrm{=1}}^{\rho },E\rangle \), whose nodes \({\mathcal{D}}\) are agents and components of a factored reward function \(f={\sum }_{e\mathrm{=1}}^{\rho }\,{f}^{e}\), and an edge \(\langle i,{f}^{e}\rangle \in E\) exists if and only if agent \(i\) influences component \({f}^{e}\).
The dependencies in a MAMAB can be described by setting \(E=\{\langle i,{f}^{e}\rangle |i\in {{\mathcal{D}}}^{e}\}\).
In this setting, the objective is to minimize the expected cumulative regret22, which is the cost incurred when pulling a particular joint arm instead of the optimal one.
Definition 3. The expected cumulative regret of pulling a sequence of joint arms until time step \(T\) according to policy \(\pi \) is
with
where \({{\boldsymbol{a}}}_{\ast }\) is the optimal joint arm and \({{\boldsymbol{a}}}_{t}\) is the joint arm pulled at time \(t\). For the sake of brevity, we will omit \(\pi \) when the context is clear.
Cumulative regret can be minimized by using a policy that considers the full joint arm space, thereby ignoring loose couplings between agents. This leads to a combinatorial problem, as the joint arm space scales exponentially with the number of agents. Therefore, loose couplings need to be taken into account whenever possible.
Multi-agent Thompson sampling
We propose the multi-agent Thompson sampling (MATS) algorithm for decision making in loosely-coupled multi-agent multi-armed bandit problems. Consider a MAMAB with groups \({{\mathcal{D}}}^{e}\) (Definition 1). The local means \({\mu }^{e}({{\boldsymbol{a}}}^{e})\) are treated as unknown. According to the Bayesian formalism, we exert our beliefs over the local means \({\mu }^{e}({{\boldsymbol{a}}}^{e})\) in the form of a prior, \({Q}_{{{\boldsymbol{a}}}^{e}}^{e}(\cdot )\). At each time step \(t\), MATS draws a sample \({\mu }_{t}^{e}({{\boldsymbol{a}}}^{e})\) from the posterior for each group and local arm given the history, \({ {\mathcal H} }_{t-1}\), consisting of local actions and rewards associated with past pulls:
Note that during this step, MATS samples directly the posterior over the unknown local means, which implies that the sample \({\mu }_{t}^{e}({{\boldsymbol{a}}}^{e})\) and the unknown mean \({\mu }^{e}({{\boldsymbol{a}}}^{e})\) are independent and identically distributed at time step \(t\).
Thompson sampling (TS) chooses the arm with the highest sample, i.e.,
However, in our case, the expected reward is decomposed into several local means. As conflicts between overlapping groups will arise, the optimal local arms for an agent in two groups may differ. Therefore, we must define the argmax-operator to deal with the factored representation of a MAMAB, while still returning the full joint arm that maximizes the sum of samples, i.e.,
To this end, we use variable elimination (VE), which computes the joint arm that maximizes the global reward without explicitly enumerating over the full joint arm space8. Specifically, VE consecutively eliminates an agent from the coordination graph, while computing its best response with respect to its neighbours. VE is guaranteed to return the optimal joint arm and has a computational complexity that is combinatorial in terms of the induced width of the graph, i.e., the number of neighbours of an agent at the time of its elimination. However, as the method is typically applied to a loosely-coupled coordination graph, the induced width is generally much smaller than the size of the full joint action space, which renders the maximization problem tractable8,9. Approximate efficient alternatives exist, such as max-plus23, but using them will invalidate the proof for the Bayesian regret bound (Theorem 1).
Finally, the joint arm that maximizes Eq. 5, \({{\boldsymbol{a}}}_{t}\), is pulled and a reward \({f}_{t}^{e}({{\boldsymbol{a}}}_{t}^{e})\) will be obtained for each group. MATS is formally described in Algorithm 1.
MATS belongs to the class of probability matching methods24.
Definition 4. Probability matching is a decision strategy which chooses an arm with the same probability as that arm being optimal, given history \({ {\mathcal H} }_{t-1}\), i.e.,
where \({{\boldsymbol{a}}}_{\ast }\) is the optimal arm and \({{\boldsymbol{a}}}_{t}\) is the pulled arm at time \(t\).
Intuitively, MATS samples the local mean rewards according to the beliefs of the user at each time step, and maximizes over those means to find the optimal joint arm according to Definition 1. This process is conceptually similar to traditional TS21.
Bayesian regret analysis
Many multi-agent systems are composed of locally connected agents. When formalized as a MAMAB (Definition 1), our method is able to exploit these local structures during the decision process. We provide a regret bound for MATS that scales sublinearly with a factor \(\tilde{A}T\), where \(\tilde{A}\) is the number of local arms.
Consider a MAMAB \(\langle {\mathcal{D}},{\mathcal{A}},f\rangle \) with \(\rho \) groups and the following assumption on the rewards:
Assumption 1. The global rewards have a mean between 0 and 1, i.e.,
Assumption 2. The local rewards shifted by their mean are \(\sigma \)-subgaussian distributed, i.e., \({\rm{\forall }}e\in [1..\rho ],{{\boldsymbol{a}}}^{e}\in {{\mathcal{A}}}^{e}\),
We maintain the pull counters \({n}_{t-1}^{e}({{\boldsymbol{a}}}^{e})\) and estimated means \({\hat{\mu }}_{t-1}^{e}({{\boldsymbol{a}}}^{e})\) for local arms \({{\boldsymbol{a}}}^{e}\).
Consider the event \({ {\mathcal E} }_{T}\), which states that, until time step \(T\), the differences between the local sample means and true means are bounded by a time-dependent threshold, i.e.,
with
where \(\delta \) is a free parameter that will be chosen later. We denote the complement of the event by \({\bar{ {\mathcal E} }}_{T}\).
Lemma 1. (Concentration inequality) The probability of exceeding the error bound on the local sample means is linearly bounded by \(\tilde{A}T\delta \). Specifically,
Proof. Using the union bound (U), we can bound the probability of observing event \({\bar{ {\mathcal E} }}_{T}\) as
The estimated mean \({\hat{\mu }}_{t-1}^{e}({{\boldsymbol{a}}}^{e})\) is a weighted sum of \({n}_{t-1}^{e}({{\boldsymbol{a}}}^{e})\) random variables distributed according to a \(\sigma \)-subgaussian with mean \({\mu }^{e}({{\boldsymbol{a}}}^{e})\). Hence, Hoeffding’s inequality (H) is applicable25.
Therefore, the following concentration inequality on \({\bar{ {\mathcal E} }}_{T}\) holds:
Lemma 2. (Bayesian regret bound under \({ {\mathcal E} }_{T}\)) Provided that the error bound on the local sample means is never exceeded until time \(T\), the Bayesian regret bound, when using the MATS policy \(\pi \), is of the order
Proof. Consider this upper bound on the sample means:
Given history \({ {\mathcal H} }_{t-1}\), the statistics \({\hat{\mu }}_{t-1}^{e}({{\boldsymbol{a}}}^{e})\) and \({n}_{t-1}^{e}({{\boldsymbol{a}}}^{e})\) are known, rendering \({u}_{t}(\cdot )\) a deterministic function. Therefore, the probability matching property of MATS (Eq. 6) can be applied as follows:
Hence, using the tower-rule (T), the regret can be bounded as
Note that the expression \(\mu ({{\boldsymbol{a}}}_{\ast })-{u}_{t}({{\boldsymbol{a}}}_{\ast })\) is always negative under \({ {\mathcal E} }_{T}\), i.e.,
while \({u}_{t}({{\boldsymbol{a}}}_{t})-\mu ({{\boldsymbol{a}}}_{t})\) is bounded by twice the threshold \({c}_{t}^{e}({{\boldsymbol{a}}}^{e})\), i.e.,
Thus, Eq. 16 can be bounded as
where \( {\mathcal I} \{\cdot \}\) is the indicator function. The terms in the summation are only non-zero at the time steps when the local action \({{\boldsymbol{a}}}^{e}\) is pulled, i.e., when \( {\mathcal I} \{{{\boldsymbol{a}}}_{t}^{e}={{\boldsymbol{a}}}^{e}\mathrm{\}=1}\). Additionally, note that only at these time steps, the counter \({n}_{T}^{e}({{\boldsymbol{a}}}^{e})\) increases by exactly 1. Therefore, the following equality holds:
The function \(\sqrt{{k}^{-1}}\) is decreasing and integrable. Hence, using the right Riemann sum,
Combining Eqs. 19–21 leads to a bound
We use the relationship \(||{\bf{x}}{||}_{1}\le \sqrt{n}||{\bf{x}}{||}_{2}\) between the 1- and 2-norm of a vector \({\bf{x}}\), where \(n\) is the number of elements in the vector, as follows:
Finally, note that the sum of all counts \({n}_{T}^{e}({{\boldsymbol{a}}}^{e})\) is equal to the total number of local pulls done by MATS until time \(T\), i.e.,
Using the Eqs. 22–24, the complete regret bound under \({ {\mathcal E} }_{T}\) is given by
Theorem 1.Let \(\langle {\mathcal{D}},{\mathcal{A}},f\rangle \)be a MAMAB. If Assumptions 1 and 2 hold, then the MATS policy \(\pi \)satisfies a Bayesian regret bound of
Proof. Using the law of excluded middle (M) and the fact that \(\Delta ({{\boldsymbol{a}}}_{t})\) and \(P({{\mathcal{E}}}_{T}|{{\mathcal{H}}}_{t-1})\) are between 0 and 1 (B), the regret can be decomposed as
Then, according to Lemmas 1 and 2 (L), we have
Finally, choosing \(\delta =(\tilde{A}T{)}^{-2}\), we conclude that
Corollary 1.If \(|{{\mathcal{A}}}_{i}|\le k\)for all agents \(i\), and if \(|{{\mathcal{D}}}^{e}|\le d\)for all groups \({{\mathcal{D}}}^{e}\), then
Proof. \(\mathop{A}\limits^{ \sim }={\sum }_{e=1}^{\rho }|{{\mathcal{A}}}^{e}|={\sum }_{e=1}^{\rho }{\prod }_{i\in {{\mathcal{D}}}^{e}}|{{\mathcal{A}}}_{i}|\le \rho {k}^{d}\).
Corollary 1 tells us that the regret is sub-linear in terms of time \(T\) and low-order polynomial in terms of the largest action space of a single agent when the number of groups and agents per group are small. This reflects the main contribution of this work. When agents are loosely coupled, the effective joint arm space is significantly reduced, and MATS provides a mechanism that efficiently deals with such settings. This is a significant improvement over the established classic regret bounds of vanilla TS when the MAMAB is ‘flattened’ and the factored structure is neglected24,26. The classic bounds scale exponentially with the number of agents, which renders the use of vanilla TS unfeasible in many multi-agent environments.
Experiments
We evaluate the performance of MATS on the benchmark problems proposed in the paper that introduced MAUCE14, which is the current state-of-the-art algorithm for multi-agent bandit problems, and one novel setting that falls outside the domain of the theoretical guarantees for both MAUCE and MATS. First, we evaluate the performance of MATS on two benchmarks that were introduced in the MAUCE paper, i.e., Bernoulli 0101-Chain and Gem Mining. We compare against a random policy (rnd), Sparse Cooperative Q-Learning (SCQL)27 and the state-of-the-art algorithm, MAUCE14. For SCQL and MAUCE, we use the same exploration parameters as in previous work14. For MATS, we always use non-informative Jeffreys priors, which are invariant toward reparametrization of the experimental settings28. Although including additional prior domain knowledge could be useful in practice, we use well-known non-informative priors in our experiments to compare fairly with other state-of-the-art techniques. Then, we introduce a novel variant of the 0101-Chain with Poisson-distributed local rewards. A Poisson distribution is supergaussian, meaning that its tails tend slower towards zero than the tails of any Gaussian. Therefore, both the assumptions made in Theorem 1 and in the established regret bound of MAUCE are violated. Additionally, as the rewards are highly skewed, we expect that the use of symmetric exploration bounds in MAUCE will often lead to either over- or underexploration of the local arms. We assess the performance of both methods on this benchmark.
Bernoulli 0101-chain
The Bernoulli 0101-Chain consists of \(n\) agents and \(n-1\) local reward distributions. Each agent can choose between two actions: 0 and 1. In the coordination graph, agents \(i\) and \(i+1\) are connected to a local reward \({f}^{i}({a}_{i},{a}_{i+1})\). Thus, each pair of agents should locally coordinate in order to find the best joint arm. The local rewards are drawn from a Bernoulli distribution with a different success probability per group. These success probabilities are given in Table 1. The optimal joint action is an alternating sequence of zeros and ones, starting with 0. In this work, we set the number of agents \(n\) to 10.
To ensure that the assumptions made in the regret analyses of MAUCE and MATS hold, we divide the local rewards by the number of groups, such that the global rewards are between 0 and 1.
We provide non-informative Jeffreys priors on the unknown means to MATS, which for the Bernoulli likelihood is a Beta prior, \( {\mathcal B} (\alpha =0.5,\beta =\mathrm{0.5)}\)29. The results for the Bernoulli 0101-chains are shown in Fig. 1(a).
Gem mining
In the Gem Mining problem, a mining company wants to excavate a set of mines for gems (i.e., local rewards). The goal is to maximize the total number of gems found over all mines. However, the company’s workers live in separate villages (i.e., agents), and only one van per village is available. Therefore, each village needs to decide to which mine it should send its workers (i.e., local action). Moreover, workers can only commute to nearby mines (i.e., coordination graph). Hence, a group can be constructed per mine, consisting of all agents that can travel toward the mine. An example of a coordination graph is given in Fig. 2
The reward is drawn from a Bernoulli distribution, where the probability of finding a gem at a mine is \({1.03}^{w-1}p\) with \(w\) the number of workers at the mine and \(p\) a base probability that is sampled uniformly random from the interval \(\mathrm{[0,0.5]}\) for each mine. When more workers are excavating a mine, the probability of finding a gem increases. Each village is populated by a number sampled uniformly random from \(\mathrm{[1..5]}\). The coordination graph is generated by sampling for each village \(i\) a number of mines \({m}_{i}\) in \(\mathrm{[2..4]}\) to which it should be connected. Then, each village \(i\) is connected to the mines \(i\) to \((i+{m}_{i}-\mathrm{1)}\). The last village is always connected to 4 mines.
We provide non-informative Jeffreys priors on the unknown means to MATS, which for the Bernoulli likelihood is a Beta prior, \( {\mathcal B} (\alpha =0.5,\beta =\mathrm{0.5)}\)29. The results for the Gem Mining problem are shown in Fig. 1(b).
Poisson 0101-chain
We introduce a novel benchmark with Poisson distributed local rewards, for which the established regret bounds of MATS and MAUCE do not hold. Similar to the Bernoulli 0101-Chain, agents need to coordinate their actions in order to obtain an alternating sequence of zeroes and ones. However, as the rewards are highly skewed and supergaussian, this setting is much more challenging. The means of the Poisson distributions are given in Table 2. We also divide the rewards by the number of groups, similar to the Bernoulli 0101-Chain. Again, we set the number of agents n to 10.
For MAUCE, an exploration parameter must be chosen. This exploration parameter denotes the range of the observed rewards. As a Poisson distribution has unbounded support, we rely on percentiles of the reward distribution. Specifically, as 95% of the rewards when pulling the optimal arm falls below 1, we choose 1 as the exploration parameter of MAUCE. For MATS we use non-informative Jeffreys priors on the unknown means, which for the Poisson likelihood is a Gamma prior, \({\mathcal{G}}(\alpha =0.5,\beta =0)\)29. The results are shown in Fig. 1(c).
Wind farm control application
We demonstrate the benefits of MATS on a state-of-the-art wind farm simulator and compare its performance to MAUCE and SCQL. A wind farm consists of a group of wind turbines, instantiated to extract energy from wind. From the perspective of a single turbine, aligning with the incoming wind vector usually ensures the highest productivity. However, translating this control policy directly towards an entire wind farm may be sub-optimal. As wind passes through the farm, downstream turbines observe a significantly lower wind speed. This is known as the wake effect, which is due to the turbulence generated behind operational turbines.
In recent work, the possibility of deflecting wake away from the farm through rotor misalignment is investigated11. While a misaligned turbine produces less energy on its own, the group’s total productivity is increased. Physically, the wake effect reduces over long distances, and thus, turbines tend to only influence their neighbours. We can use this domain knowledge to define groups of agents and organize them in a graph structure. Note that the graph structure depends on the incoming wind vector. Nevertheless, atmospheric conditions are typically discretized when analyzing operational regimes30, thus, a graph structure can be made independently for each possible incoming discretized wind vector. We construct a graph structure for one possible wind vector.
We demonstrate our method on a virtual wind farm, consisting of 11 turbines, of which the layout is shown in Fig. 3. We use the state-of-the-art WISDEM FLORIS simulator31. Each turbine is an agent, and choosing an orientation with respect to the incoming wind vector corresponds to an action. The groups are constructed according to the graph depicted in Fig. 3. The reward is described by the power production per agent, which we divide uniformly over the groups that the agent is part of. The objective is to find the joint alignment of the wind farm that maximizes the total power production.
For MATS, we assume the local power productions are sampled from Gaussians with unknown mean and variance, which leads to a Student’s t-distribution on the mean when using a Jeffreys prior32. The results for the wind farm control setting are shown in Fig. 4.
Discussion
MATS is a Bayesian method, which means that it can leverage prior knowledge about the data distribution. This property is highly beneficial in many practical applications, e.g., influenza mitigation18,19 and wind farm control4.
Both MAUCE and MATS achieve sub-linear regret in terms of time and low-order polynomial regret in terms of the number of local arms for sparse coordination graphs. However, empirically, MATS consistently outperforms MAUCE as well as SCQL. We can see that MATS solves the Bernoulli 0101-Chain problem in only a few time steps, while MAUCE still pulls many sub-optimal actions after 10000 time steps (see Fig. 1(a)). In the more challenging Gem Mining problem, the cumulative regret of MAUCE is three times as high as the cumulative regret of MATS around 40000 time steps (see Fig. 1(b)). In the wind farm control task, we can see that MATS allowed for a five-fold increase of the normalized power productions with respect to the state of the art (see Fig. 4).
We argue that the high performance of MATS is due to the ability to seamlessly include domain knowledge about the shape of the reward distributions and treat the problem parameters as unknowns. To highlight the power of this property, we introduced the Poisson 0101-chain. In this setting, the reward distributions are highly skewed, for which the mean does not match the median. Therefore, in our case, since the mean falls well above 50% of all samples, it is expected that for the initially observed rewards, the true mean will be higher than the sample mean. Naturally, this bias averages out in the limit, but may have a large impact during the early exploration stage. The high standard deviations in Fig. 1(c) support this impact. Although the established regret bounds of MATS and MAUCE do not apply for supergaussian reward distributions, we demonstrate that MATS exploits density information of the rewards to achieve more targeted exploration. In Fig. 1(c), the cumulative regret of MATS stagnates around 7500 time steps, while the cumulative regret of MAUCE continues to increase significantly. As MAUCE only supports symmetric exploration bounds, it is challenging to correctly assess the amount of exploration needed to solve the task.
Throughout the experiments, exploration constants had to be specified for MAUCE, which were challenging to choose and interpret in terms of the density of the data. In contrast, MATS uses either statistics about the data (if available) or, potentially non-informative, beliefs defined by the user. For example, in the wind farm case, the spread of the data is unknown. MATS effectively maintains a posterior on the variance and uses it to balance exploration and exploitation, while still outperforming MAUCE with a manually calibrated exploration range (see Fig. 4).
Currently, we established an upper bound on the cumulative regret to show that MATS learns the optimal action eventually (i.e., the cumulative regret reduces sub-linearly over time) and effectively exploits the sparse structure of the joint action space (i.e., the regret bound is in terms of the number of local joint actions instead of the global joint actions). In future work, we will aim to construct a lower bound for MATS, which will allow us to assess the tightness of the established upper bound.
Related work
Multi-agent reinforcement learning and planning with loose couplings has been investigated in sequential decision problems9,33,34,35. In sequential settings, the value function cannot be factorized exactly. Therefore, it is challenging to provide convergence and optimality guarantees. While for planning some theoretical guarantees can be provided35, in the learning literature the focus has been on empirical validation33. In this work, we focus on MAMABs, which are single-shot stateless problems. In such settings, the reward function is factored exactly into components that only depend on a subset of agents.
The combinatorial bandit36,37,38,39 is a variant of the multi-armed bandit, in which, rather than one-dimensional arms, an arm vector has to be pulled. In our work, the arms’ dimensionality corresponds to the number of agents in our system, and similarly to combinatorial bandits, the number of arms exponentially increases with this quantity. We consider a variant of this framework, called the semi-bandit problem40, in which local components of the global reward are observable. Chen et al.39 constructed an algorithm for this setting that assumes access to an \((\alpha ,\beta )\)-oracle, which provides a joint action that outputs a fraction \(\alpha \) of the optimal expected reward with probability \(\beta \). Instead, we assume the availability of a coordination graph, which we argue is a reasonable assumption in many multi-agent settings.
Sparse cooperative Q-learning is an algorithm that also assumes the availability of a coordination graph27. However, although strong experimental results are given, no theoretical guarantees were provided. Later, the UCB-like algorithm, HEIST, for exploration and exploitation in MAMABs was introduced20, which uses a message-passing scheme for resolving coordination graphs. They provide some theoretical guarantees on the regret for problems with acyclic coordination graphs. Multi-Agent Upper-Confidence Exploration (MAUCE)14 is a more general method that uses variable elimination to resolve (potentially cyclic) coordination graphs. MAUCE demonstrates high performance on a variety of benchmarks and provides a tight theoretical upper bound on the regret. MATS provides a Bayesian alternative to MAUCE based on Thompson sampling (TS).
Our problem definition is related to distributed constraint optimization (DCOP) problems41. In DCOP problems, multiple agents control a set of variables in a distributed manner under a set of constraints. The objective is the same as for a MAMAB, i.e., optimize the sum over group rewards. However, in DCOPs, the rewards are assumed to be known beforehand. The Distributed Coordination of Exploration and Exploitation (DCEE) framework42 extends this setting to unknown rewards, but considers the optimization of the cumulative reward achieved over a time span, rather than of a single-step reward. MAMABs, or MAB-DCOPs20, consider the optimization of a single-step expected reward over time.
In recent research on wind farm control, the impact of optimized rotor alignments on power production is heavily investigated11. To search for the optimal alignments within the wind farm, data-driven methods are usually adopted, where the turbines’ alignments are perturbed iteratively until they locally converge12. When optimizing the alignment of a wind turbine, only considering its neighbours can significantly boost the learning speed3. MATS is also able to leverage neighbourhood structures. In addition, rather than random perturbation of the alignments, MATS leverages an exploration-exploitation mechanism that is inspired by TS and variable elimination, which allows for a global exploration mechanism that targets the optimal alignment configuration, while retaining a small regret during the learning process itself.
Statement of reproducibility
The source code of all experiments is publicly available at: https://github.com/timo-verstraeten/mats-experiments.
Conclusions
We proposed multi-agent Thompson sampling (MATS), a novel Bayesian algorithm for multi-agent multi-armed bandits. The method exploits loose connections between agents to solve multi-agent coordination tasks efficiently. Specifically, we proved that, for \(\sigma \)-subgaussian rewards with bounded means, the expected cumulative regret decreases sub-linearly in time and low-order polynomially in the highest number of actions of a single agent when the coordination graph is sparse. Empirically, we showed a significant improvement over the state-of-the-art algorithm, MAUCE, on several synthetic benchmarks. Additionally, we showed that MATS can seamlessly be adapted to the available prior knowledge, and achieves state-of-the-art performance on the Poisson 0101-Chain, a new benchmark with supergaussian rewards. Finally, we demonstrated that MATS achieves high performance on a realistic wind farm control task, where the optimal rotor alignments of the wind turbines need to be jointly optimized to maximize the farm’s power production. In many practical applications, there exist sparse neighbourhood structures between agents, and we have shown that MATS is able to successfully exploit these structures, while leveraging prior knowledge about the data.
References
Wiering, M. Multi-agent reinforcement learning for traffic light control. In Proceedings of the 17th International Conference on Machine Learning (ICML), 1151–1158 (2000).
Claes, D., Oliehoek, F., Baier, H. & Tuyls, K. Decentralised online planning for multi-robot warehouse commissioning. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 492–500 (International Foundation for Autonomous Agents and Multiagent Systems, 2017).
Gebraad, P. M. & van Wingerden, J.-W. Maximum power-point tracking control for wind farms. Wind. Energy 18, 429–447 (2015).
Verstraeten, T. et al. Fleetwide data-enabled reliability improvement of wind turbines. Renew. Sustain. Energy Rev. 109, 428–437 (2019).
Boutilier, C. Planning, learning and coordination in multiagent decision processes. In TARK 1996: Proceedings of the 6 th conference on Theoretical aspects of rationality and knowledge, 195–210 (1996).
Koller, D. & Parr, R. Policy iteration for factored MDPs. In Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence (UAI), 326–334 (Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2000).
Guestrin, C., Koller, D. & Parr, R. Max-norm projections for factored MDPs. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI), 673–682 (2001).
Guestrin, C., Koller, D. & Parr, R. Multiagent planning with factored mdps. In Advances in Neural Information Processing Systems (NIPS) 14, 1523–1530 (2001).
Guestrin, C., Venkataraman, S. & Koller, D. Context-specific multiagent coordination and planning with factored mdps. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI), 253–259 (2002).
Chapman, A. C., Leslie, D. S., Rogers, A. & Jennings, N. R. Convergent learning algorithms for unknown reward games. SIAM J. on Control. Optim 51, 3154–3180 (2013).
van Dijk, M. T., Wingerden, J.-W., Ashuri, T., Li, Y. & Rotea, M. A. Yaw-misalignment and its impact on wind turbine loads and wind farm power output. J. Physics: Conf. Ser. 753 (2016).
Marden, J. R., Ruben, S. D. & Pao, L. Y. A model-free approach to wind farm control using game theoretic methods. IEEE Transactions on Control. Syst. Technol 21, 1207–1214 (2013).
Verstraeten, T., Libin, P. J. K. & Ann, N. Fleet control using coregionalized gaussian process policy iteration. In Proceedings of the 24rd European Conference on Artificial Intelligence (ECAI) (2020).
Bargiacchi, E., Verstraeten, T., Roijers, D. M., Nowé, A. & Hasselt, H. Learning to coordinate with coordination graphs in repeated single-stage multi-agent decision problems. In Proceedings of the 35th International Conference on Machine Learning (ICML), 482–490 (2018).
Verstraeten, T., Bargiacchi, E., Libin, P. J. K., Roijers, D. M. & Nowé, A. Thompson sampling for factored multi-agent bandits. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (International Foundation for Autonomous Agents and Multiagent Systems, 2020).
Chapelle, O. & Li, L. An empirical evaluation of Thompson sampling. In Advances in Neural Information Processing Systems (NIPS) 24, 2249–2257 (2011).
Agrawal, S. & Goyal, N. Analysis of Thompson sampling for the multi-armed bandit problem. In Proceedings of the 25 th Annual Conference on Learning Theory (COLT), vol. 23, 39.1–39.26 (2012).
Libin, P. J. K. et al. Bayesian best-arm identification for selecting influenza mitigation strategies. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD), 456–471 (Springer, 2018).
Libin, P. J. K. et al. Thompson sampling for m-top exploration. In Proceedings of the IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI), 1414–1420 (2019).
Stranders, R., Tran-Thanh, L., Fave, F. M. D., Rogers, A. & Jennings, N. R. DCOPs and bandits: Exploration and exploitation in decentralised coordination. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 289–296 (International Foundation for Autonomous Agents and Multiagent Systems, 2012).
Thompson, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25, 285–294 (1933).
Agrawal, S. & Goyal, N. Further optimal regret bounds for Thompson sampling. In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 31, 99–107 (2013).
Vlassis, N., Elhorst, R. & Kok, J. R. Anytime algorithms for multiagent decision making using coordination graphs. In IEEE International Conference on Systems, Man and Cybernetics, vol. 1, 953–957 (2004).
Lattimore, T. & Szepesvári, C. Bandit algorithms. preprint (2018).
Vershynin, R. High-dimensional probability: An introduction with applications in data science, vol. 47 (Cambridge University Press, 2018).
Russo, D. & Van Roy, B. Learning to optimize via posterior sampling. Math. Oper. Res. 39, 1221–1243 (2014).
Kok, J. R. & Vlassis, N. Sparse cooperative q-learning. In Proceedings of the 21st International Conference on Machine Learning (ICML) (New York, NY, USA, 2004).
Robert, C. The Bayesian choice: from decision-theoretic foundations to computational implementation (Springer Science & Business Media, 2007).
Lunn, D., Jackson, C., Best, N., Spiegelhalter, D. & Thomas, A. The BUGS book: A practical introduction to Bayesian analysis (Chapman and Hall/CRC, 2012).
International Electrotechnical Commission. Wind turbines – Part 4: Design requirements for wind turbine gearboxes (No. IEC 61400-4) Accessed 6 March 2019 (2012).
NREL. FLORIS. Version 1.0.0 (2019).
Honda, J. & Takemura, A. Optimality of Thompson sampling for Gaussian bandits depends on priors. In Artificial Intelligence and Statistics, 375–383 (2014).
Kok, J. R. & Vlassis, N. Using the max-plus algorithm for multiagent decision making in coordination graphs. In Bredenfeld, A., Jacoff, A., Noda, I. & Takahashi, Y. (eds.) RoboCup 2005: Robot Soccer World Cup IX, vol. 4020 of Lecture Notes in Computer Science, 1–12 (Springer, 2006).
De Hauwere, Y.-M., Vrancx, P. & Nowé, A. Learning multi-agent state space representations. In Proceedings of the 9 th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 715–722 (International Foundation for Autonomous Agents and Multiagent Systems, 2010).
Scharpff, J., Roijers, D. M., Oliehoek, F. A., Spaan, M. T. J. & deWeerdt, M. M. Solving transition-independent multi-agent MDPs with sparse interactions. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI) (2016).
Bubeck, S. & Cesa-Bianchi, N. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations Trends Mach. Learn. 5, 1–122 (2012).
Cesa-Bianchi, N. & Lugosi, G. Combinatorial bandits. J. Comput. Syst. Sci. 78, 1404–1422 (2012).
Gai, Y., Krishnamachari, B. & Jain, R. Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. IEEE/ACM Transactions on Netw. (TON) 20, 1466–1478 (2012).
Chen, W., Wang, Y. & Yuan, Y. Combinatorial multi-armed bandit: General framework, results and applications. In Proceedings of the 30th International Conference on Machine Learning (ICML), vol. 28, 151–159 (2013).
Audibert, J.-Y., Bubeck, S. B. & Lugosi, G. Minimax policies for combinatorial prediction games. In Proceedings of the 24th Annual Conference on Learning Theory (COLT), vol. 19, 107–132 (2011).
Yokoo, M., Durfee, E. H., Ishida, T. & Kuwabara, K. The distributed constraint satisfaction problem: Formalization and algorithms. IEEE Transactions on knowledge data engineering 10, 673–685 (1998).
Taylor, M. E., Jain, M., Tandon, P., Yokoo, M. & Tambe, M. Distributed on-line multi-agent optimization under uncertainty: Balancing exploration and exploitation. Adv. Complex Syst. 14, 471–528 (2011).
Acknowledgements
The authors would like to acknowledge FWO (Fonds Wetenschappelijk Onderzoek) for their support through the SB grants of Timothy Verstraeten (#1S47617N), Eugenio Bargiacchi (#1SA2820N) and Pieter J.K. Libin (#1S31916N). This research was supported by funding from the Flemish Government under the “Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen” programme and under the VLAIO Supersized 4.0 ICON project.
Author information
Authors and Affiliations
Contributions
T.V. performed the theoretical regret analysis, E.B. wrote the source code for the experiments, T.V., E.B. and P.L. designed and conducted the experiments, T.V., E.B., P.L. and D.R. analysed the results, P.L. and D.R. provided advice on the methodology, J.H. provided advice on the wind farm control case, and D.R., J.H. and A.N. supervised the project. T.V. wrote the manuscript and all authors reviewed the manuscript.
Corresponding author
Ethics declarations
Competing interests
The authors declare no competing interests.
Additional information
Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Verstraeten, T., Bargiacchi, E., Libin, P.J.K. et al. Multi-Agent Thompson Sampling for Bandit Applications with Sparse Neighbourhood Structures. Sci Rep 10, 6728 (2020). https://doi.org/10.1038/s41598-020-62939-3
Received:
Accepted:
Published:
DOI: https://doi.org/10.1038/s41598-020-62939-3
- Springer Nature Limited