Coordinated Versus Decentralized Exploration In Multi-Agent Multi-Armed Bandits

1 Introduction

The past decade has seen an increased use of robotic and software agents; more companies and labs are creating their own agents that have different operating strategies and, in many cases, may need to work together as a team in order to achieve certain objectives. This world of increasing interdependence has motivated the research area of ad hoc teamwork [Stone and Kraus, 2010]: a setting in which agents need to cooperate without any pre-coordination and work toward a common goal [Stone et al., 2010]. Standard approaches to teamwork, e.g. SharedPlans [Grosz and Kraus, 1996], STEAM [Tambe, 1997], or GPGP [Decker and Lesser, 1995], rely on common agreements about strategies and communication standards, or other shared assumptions. However, in ad hoc teamwork, teammates should be able to leverage each others' knowledge without explicitly relying on the strategy used to generate that knowledge, or assumptions about how others will operate in the future. This is a grand challenge for the state of the art in multi-agent systems, but the multi-armed bandit (MAB) domain has emerged in the last few years as the standard approach to start thinking about it [Barrett et al., 2014].

In a multi-agent multi-armed bandit problem, a team of agents (e.g. a swarm of nanorobots performing a complex set of tasks or of drones patrolling a large area, etc.) is playing a MAB. The question that makes this problem interesting beyond the intrinsic exploration / exploitation tradeoff feature of the single-agent version is the role of information sharing. Although various solutions to classical MAB problems are well known [Gittins and Jones, 1979; Gittins, 1979; Auer et al., 2002a; Auer et al., 1995; Lai and Robbins, 1985] and the agents may individually play such a solution to converge on a good strategy, it is intuitively clear that by sharing information, e.g. about their observed payoffs in past rounds, they can approach a good strategy much faster. But, in general, information sharing comes at a cost that can take many forms: for example, a fixed penalty term or fractional reduction applied to the immediate reward gathered from a pull, or the preclusion of pulling an arm while while an agent transmits a message to its teammates. In this paper, we devise and evaluate a solution scheme for the last scenario in the above list: if an agent communicates, it cannot simultaneously access the bandit, thus incurring an opportunity cost. However, the scheme generalizes to other definitions of cost.

We first define a new multi-agent MAB model, in order to capture the three-way tradeoff between exploration, exploitation, and communication. We benchmark the performance that can be achieved in a centralized version of this problem (with Gaussian rewards) in which a controller with knowledge of each agent's choices and rewards can decide which agents to allocate to pulling which arm without suffering any communication cost. Intuitively, one would expect that under such circumstances, it should be possible to achieve a total reward that is close to what is attainable in the full-information experts learning or forecasting variant of the problem [Vovk, 1990; Foster, 1991; Foster and Vohra, 1993; Littlestone and Warmuth, 1994]. We establish that a multiagent strategy with a centralized coordinator (with costless communication), which we call the public agent, can indeed obtain performance similar to these single-agent solutions that use full information. Our method is based on multiplicative weight updates, and we prove a regret bound for this strategy using a technique due to Freund and Schapire [1999].

The problem that we actually want to solve involves a decentralized (albeit cooperative) multi-agent system; but the insights we gain from the analysis of the idealized version with a central controller turn out to be useful in designing effective protocols for how these agents communicate and utilize publicly available information. We let the teammaintain a shared base of all historically broadcast information that acts as a proxy for the public agent in the following sense: Whenever an agent decides which arm to pull, it does so based on a combination of its private information with that in this shared base; whenever an agent decides whether or not to broadcast and hence has to reason about the long-term impact of its immediate future action on the performance of the team, it approximates the team's future behavior by that of an imaginary controller having access to the shared information base and allocating arms as in the centralized version.

More precisely, the exploration-exploitation strategy in our decentralized algorithm is a variant of the softmax approach, which is known to perform well empirically for the single-agent problem [Vermorel and Mohri, 2005]: The agent chooses an arm according to a distribution of probabilities proportional to the exponentials of the empirical rewards obtained from the arms, weighted appropriately. In our multiagent extension, each agent chooses an arm using a similar weight distribution whose parameters are informed by the algorithm we developed for the central benchmark. To summarize our procedure for deciding when to broadcast, which we call the "Value of Information" (VoI) communication strategy, an agent optimistically estimates the total reward that could possibly result from broadcasting its latest observation, which is then compared to the estimated reward from pulling an arm. If the latter is higher, then the agent naturally abstains from broadcasting in the next round; otherwise, it communicates with a probability chosen so that in expectation approximately one of the agents that pulled that arm is communicating in a given round (specifically, a probability inversely proportional to the expected number of agents in the population that pulled the arm, given the current empirical estimates). Finally, we show experimentally that our decentralized algorithm for the multi-agent MAB achieves performance close to that of the centralized algorithm, thus efficiently solving the exploration / exploitation / communication "trilemma".

2 RelatedWork

Stone and Kraus [2010] were the first to use a MAB model for ad hoc teamwork (a simple two-agent cooperative setting), but Barrett et al. [2014] used a multi-agent MAB (in particular, a two-armed bandit with Bernoulli payoff distributions) to formalize ad hoc teamwork with costly communication for the first time: They focused on designing a single ad hoc agent that can learn optimal strategies when playing with teammates who have specified strategies, in a setting where each round consists of a communication phase (broadcasting a message with an associated cost function), and an action phase (pulling an arm to extract a reward). More recent work has focused on designing adaptive ad hoc agents that can observe (previously unseen) teammates during operation but cannot exchange messages with them (e.g.

[Albrecht and Ramamoorthy, 2013; Barrett and Stone, 2015; Hernandez-Leal et al., 2016] and references therein). We, on the other hand, construct a common communication protocol for every agent in a decentralized teamwhere information sharing is feasible but optional and, if executed, precludes action. This also differentiates our contribution from the distributed stochastic bandit algorithm [Sz¨or´enyi et al., 2013] for a P2P network where each pull of an arm is necessarily followed by message passing between peers.

Some previous work has modeled communication cost in a collaborative multi-agent system as an extraneous quantity, equal or proportional to the number "of messages sent in the system", that is traded off against regret (in the reward collected from the bandit), in both (distributed) experts [Kanade et al., 2012] and MAB [Hillel et al., 2013; Buccapatnam et al., 2015] settings; in our model, information sharing interferes more intimately with reward collection. Distributed multi-agent MABs have also been employed to model cognitive radio networks [Liu and Zhao, 2010; Kalathil et al., 2012; Tossou and Dimitrakakis, 2015] where collisions (multiple agents pulling the same arm in the same round) are costly. In our model, multiple agents pulling the same arm all receive the same reward for that round. A fundamentally different application of the MAB model to multi-agent systems is the use of MAB policies by agents to select other agents for specific services within a service sharing system [Vall´ee et al., 2014]. Both theoretical and experimental studies of social learning or imitation in the social and cognitive sciences have involved multi-agent MAB models, where agents access and utilize one another's historical information [Schlag, 1998; Biele et al., 2009; Rendell et al., 2010]. The main difference with our model is that their agents are selfishly motivated whereas ours work towards the shared goal of maximizing the collective reward. Moreover, in these models, no cost is incurred by an agent for transmitting information but may be sustained in acquiring it; e.g., if an agent is receiving (perhaps noisy) information about another's action and reward, it cannot pull an arm in that epoch.

3 Formal ProblemDescription

Our model follows the basic definitions of a classical bandit problem: We have a set of n arms such that, in any epoch t over a pre-specified time-horizon of length T, arm i generates a random reward ri,t independently (across arms and epochs) from a time-invariant Gaussian distribution: ri,t ∼ N(µi, σ2 ) ∀i, t. We assume that all arms have the same known standard deviation σ > 0 but unknown means {µi}ni=1 , where µi ̸= µj for at least one pair (i, j), and that the maximum and minimum possible values, µmax > µmin > 0, of these mean rewards are also known a priori.

There are m > n agents in our team: In epoch t, each agent j must decide without any knowledge of the others' simultaneous decisions whether to broadcast a message consisting of the index of the arm it pulled and the reward it thus gained in epoch (t - 1). If an agent chooses to broadcast at t, then it loses the chance to pull any arm and hence collect any reward during t - this can be viewed as the cost of communication - but its message becomes available to the entire team for use in decision-making from epoch (t + 1) onwards. However if an agent decides not to broadcast at t, it pulls an arm and gets a reward. If multiple agents pull the same arm i in epoch t, each receives the same reward ri,t; the fact that an arm generates the same reward regardless of howmany times it is pulled in an epoch removes any learning benefit from an arm being pulled by more than one agent at any t.

Thus, if mi,t agents pull arm i in epoch t, then ∑ni=1 mi,t ≤ m in general, and the total reward amassed by the team in this epoch is ∑ni=1 mi,tri,t. Every agent's goal is to maximize the team's cumulative total reward over T epochs, i.e. ∑Tt=1 ∑ni=1 mi,tri,t. This is why broadcasting can be beneficial in the long run: By sacrificing immediate gain, an agent enriches the shared pool of knowledge about the unknown parameters, leading to savings in exploration time for the team as a whole. However, each agent now has to resolve a two-stage dilemma: [Stage 1 (Communication vs Reward Collection)] Should it broadcast its observation from the previous epoch? [Stage 2 (Exploration vs Exploitation)] If it decides not to broadcast, which arm should it pull now?

Before presenting our strategy for handling the above issues in Section 5, we describe in Section 4 an idealized version of our problem in which a central authority that we call the public agent always has complete knowledge of rewards generated by all arms, and uses that to allocate arms to agents that do not make individual decisions. We then propose and analyze a multiplicative weights update algorithm to solve this exploration-exploitation problem with instantaneous costless communication. This framework serves a dual purpose: It offers insights that we utilize in the design of our solution scheme for the decentralized problem, and also provides a gold standard for evaluating that scheme.

4 Ideal CentralizedMulti-Agent MAB

The public agent maintains a normalized weight (in other words, probability) distribution across the n arms, denoted by Pt = (P1,t, P2,t, · · · , Pn,t) where Pi,t ≥ 0 ∀i, ∑ni=1 Pi,t = 1, and assigns mPi,t agents to arm i in epoch t. 1 The starting distribution is uniform: Pi,1 = 1/n ∀i. During t, the public agent observes the sample reward ri,t generated by each arm i, and hence updates the weight distribution to Pt+1 at the beginning of the next epoch using the following multiplicative weights update (MWU) approach [Littlestone and Warmuth, 1994; Freund and Schapire, 1997; Freund and Schapire, 1999]:

where β ∈ (0, 1), λ ∈ R, κ > 0, Zt = ∑nι=1 Pι,tβ- rι,t+λ κ . Ideally, the public agent would like to maximize the cumulative reward of the team over a given time-horizon T , i.e. ∑Tt=1 ∑ni=1 ri,tmPi,t, or equivalently the time-averaged peragent cumulative reward 1 T ∑Tt=1 ri,tPi,t. We define the regret of the centralized strategy with updates (1) as

1 In an actual implementation, if mPi,t is fractional, then ⌊mPi,t⌋ agents are initially assigned to arm i, and then all the remaining (m-∑ni=1 ⌊mPi,t⌋) are optimistically allocated to the arm with the current highest empirical mean.

where P = (P1, P2, · · · , Pn) is a probability distribution. Theorem 1 shows that the regret of this centralized MWU method becomes vanishingly small for a large enough T .

Theorem 1 Suppose, a bandit has n arms producing Gaussian rewards with the same known standard deviation σ, and unknown means {µi}ni=1 with a known range Rµ ≜ µmax - µmin > 0. For any horizon T ∈ Z+ and an arbitrarily small number δ, 0 < δ < min{2nTΦ(Rµ/2σ), 1}, if we use a centralized MWU strategy with a uniform initial weight distribution and the update rule (1) with parameters

where Φ(·) denotes the standard normal cumulative distribution function, then with probability at least (1 - δ),

We outline the proof of the theorem below, and defer the complete proof to a full version of the paper. But first, we note that the above MWU algorithm is equivalent to a decreasing SOFTMAX strategy [Vermorel and Mohri, 2005] over empirical means ˆµi,t = ∑ts=1 ri,s/t with temperature τt = τ0/t,

Proof sketch. We rewrite the multiplicative factor in (1) as β ˆLi,t where we define ˆLi,t ≜ (-ri,t-λ)/κ as the normalized loss. We now recall the amortized analysis that Freund and Schapire [1999] used to prove that their MWU algorithm for repeated game playing is no-regret when the player's loss for any action lies in [0, 1], and adapt it to the case of Gaussian losses. We have chosen the shifting and rescaling parameters λ and κ so that the following inequality holds:

Our potential function is RE(˜P||Pt), the Kullback-Leibler divergence of the current probability distribution Pt from an arbitrary fixed distribution ˜P; we further define ∆˜ REt,t′ ≜ RE(˜P||Pt′ )-RE(˜P||Pt). It is easy to see that ∆˜ RE1,T+1 ≥ -ln(n) since P1 is a uniform distribution; combining the analysis of Freund and Schapire [1999] with a union bound of probabilities (over arms and epochs) applied to (3), we can further deduce a high-probability upper bound on ∆˜ RE1,T +1 = ∑Tt=1 ∆ ˜ REt,t+1. Using these upper and lower bounds, we can establish that, with probability at least (1-δ), 1 T ∑Tt=1 ∑ni=1 ri,t ˜ Pi - 1 T ∑Tt=1 ∑ni=1 ri,tPi,t ≤ ∆, where

∆ ≜ κ (√2 ln(n)/T + ln(n)/T ). Finally, using the Gaussian tail inequality Φ(-a) ≤ 0.5e-a2 /2 for any a > 0, we can show that κ ≤ Rµ + 2σ√2 ln( nT δ ), and hence, after some algebra, that ∆ < 2√2 (√2+1) (Rµ +σ) √ln( nT δ ) ln(n) T for T ≥ max(2, ln(n)). This completes the proof. □

5 DecentralizedMABWith Value-of-Information Communication Strategy

The decentralized problem takes away the coordinator, introducing communication as a costly option; we design a scheme for how each agent decides whether to broadcast or pull an arm such that the team's overall behavior mimics that of the centralized version (Section 4) as closely as possible. To this end, we employ a device which we will call the public agent for a decentralized MAB but which is, in fact, an identical representation held by each agent of all the information publicly communicated until the current epoch: a shared table containing two entries for each arm i, ν cum i,t = |T cum i,t |, where T cum i,t is the set of epochs at each of which information on arm i was broadcast by at least one agent until (but excluding) epoch t, and the cumulative reward rcum i,t = ∑t∈T cum i,t ri,t. The public agent's empirical mean for arm i during epoch t is ˆµpublic i,t = rcum i, t /ν cum i, t . For any agent j, any epoch is either an action round, when it pulls an arm, or a broadcast round, when it sends a message to the team, the starting epoch being necessarily an action round for every agent. Agent j has a private table with four entries for each arm i: ν a i,j,t = |T a i,j,t |, ra i,j,t = ∑t∈T a i,j,t ri,t, ν b i,j,t = |T b i,j,t |, rb i,j,t = ∑t∈T b i,j,t ri,t where T a i,j,t is the set of epochs in which agent j has pulled arm i, and T b i,j,t ⊂ T a i,j,t is the subset of these pulls that it has communicated until (but excluding) epoch t.

Exploration-exploitation with softmax strategy. If epoch t is an action round for agent j, then at the beginning of this epoch, this agent combines its private table with the public agent's information set to produce its own vector of empirical means across arms {ˆµi,j,t}ni=1 : ˆµi,j,t = ˆ ri,j,t/ˆ νi,j,t where ˆ ri,j,t = ra i,j,t -rb i,j,t +rcum i,t and ˆ νi,j,t = ν a i,j,t -ν b i,j,t +ν cum i,t . 2 It then applies a softmax function to these means with the decreasing temperature parameter τt = τ0/t, τ0 defined in (2) in Section 4, to generate a probability distribution over arms, and draws an arm according to this distribution, say i∗ = ij,t. The reward r∗ = ri∗ ,t thus collected is added to the team's cumulative reward; agent j updates its private table entries: ra i∗ ,j,t+1 = ra i∗ ,j,t + r∗ , ν a i∗ ,j,t+1 = ν a i∗ ,j,t + 1; ra i,j,t+1 = ra i,j,t , ν a i,j,t+1 = ν a i,j,t ∀i ̸= i∗ .

Value-of-Information (VoI) communication criterion. At the end of each action round, say epoch t, agent j follows a three-step (in general) procedure, depicted as flow-chart in Figure 1, to decide whether or not broadcast information on the arm i∗ it just pulled in the next epoch (t + 1).

2 Each agent's private table is so initialized that the initial empirical mean for each arm is (µmin + µmax)/2.

First, it checks if the reward r∗ from this pull is greater than the public agent's empirical mean ˆµpublic i∗ ,t ; if yes (resp. no), then it uses an upper (resp. a lower) confidence bound on the mean reward of the arm i∗ under consideration and a lower (resp. an upper) bound on that of every other arm to generate a vector of working estimates {˜ µi,j,t}ni=1 across arms for further comparison purposes: An upper (resp. lower) bound is obtained by adding to (resp. subtracting from) the updated empirical mean ˆµi,j,t+1 the quantity σ√2 ln( nT 2εvoi )/ˆ νi,j,t+1, where εvoi ∈ (0, 1) is a free (error) parameter.

In the second step, agent j uses the public agent as a proxy for the team's collective behavior to compare the team's estimated expected cumulative reward over the remainder of the horizon in two mutually exclusive and exhaustive scenarios: one in which epoch (t + 1) is an action round, say Λaj,t , and the other in which it is a broadcast round, say Λbj,t . For computing Λaj,t , agent j acts as if the public agent will receive no further communication, and will allocate arms to agents in all epochs starting at (t + 1) using the weight distribution wa t = {wa i,t }ni=1 , where the temperature τt comes from (2):

For evaluating Λbj,t , agent j assumes that the public agent uses the weight distribution wa t to allocate arms to the remaining (m- 1) agents during epoch (t + 1), after which it will augment its information set with only agent j's broadcast message (i∗ , r∗ ) to update its weight distribution to wb t+1 = {wb i,t+1 }ni=1 , and use this distribution henceforth.

The algebraic expressions for Λaj,t and Λbj,t are provided in Figure 1. Notice that the computation of Λbj,t is the only time in our scheme when the exact nature of the communication cost comes into play. For other cost types mentioned in our introduction, we will just have (an) additional term(s) to account for it in the above summation; the rest of the scheme remains the same as delineated in this paper.

Let us define the agent's current Value of Information VoI ≜ Λbj,t - Λaj,t , which estimates the long-term benefit accrued by the team if the agent under consideration forgoes immediate reward collection to share its latest information. The idea of using the value of information for decision making implicitly goes back a long way; the explicit modern formulation goes back at least to Howard [1966]. Recently, it has been used in related AI contexts by Chajewska et al. [2000] and Boutilier [2002], among others.

Agent j decides to not broadcast in epoch (t + 1) if VoI ≤ 0; if VoI > 0, it uses what we will call the simple communication criterion in the final step of its decisionmaking procedure: It estimates the number of agents ˆmi∗ that have pulled the arm i∗ in epoch t as the product of m and the public agent's current weight wa i∗ ,t on the arm; if ˆmi∗ is one or less, agent j decides to broadcast deterministically at (t + 1), otherwise it broadcasts at (t + 1) on the success of a Bernoulli trial with success probability 1/⌊ ˆmi∗⌋. The idea is to keep the expected number of broadcasts per arm per epoch at 1 since excess simultaneous broadcasts corresponding to the same arm convey redundant information and only impede reward collection. If (and only if) agent j decides that epoch (t + 1) is a broadcast round, the entries rb i∗ ,j,t and ν b i∗ ,j,t in its private table are incremented by r∗ and 1 respectively.

Message broadcasting. If epoch t is a broadcast round for agent j, it publicly sends out the message (i∗ , r∗ ) where i∗ = ij,t-1 and r∗ = ri∗ ,t-1, pulls no arm at t but sets epoch (t + 1) as an action round; before epoch (t + 1) commences, the public agent is augmented with messages transmitted by all broadcasting team members in epoch t, discarding duplicates.

6 Experimental Evaluation

In this section, we describe two sets of experiments we ran to compare the performance of the decentralized multi-agent MAB exploration-exploitation algorithm with VoI communication strategy that we proposed in Section 5 with several benchmarks described below. In these two sets, we studied the variation of the regret of each algorithm over the number of arms and over different lengths of the time-horizon (keeping the other variable fixed) respectively - we report the corresponding results in Figures 2 (a) and (b).

Our main benchmark for both sets is the centralized softmax / MWU strategy, detailed in Section 4, which gives us a lower bound on the regret achievable by any decentralized scheme. Additionally, for the first set of experiments, we used two other benchmarks - agents exploring-and-exploiting the bandit arms independently (i.e. with no communication) all using one of two standard approaches - EXP3 [Auer et al., 2002b] and UCB1-Normal [Auer et al., 2002a] - to demonstrate that regret can be lowered drastically by allowing agents to engage in broadcasting, even if the latter is expensive. Finally, for both sets, we also ran experiments where agents made their broadcasting decisions using only the simple communication criterion described in Section 5 and demarcated in Figure 1 (skipping the first two stages of VoI) in order to show the improvement, if any, that can be achieved by incorporating the value of information (i.e. the difference Λbj,t - Λaj,t ) in one's decision-making process.

For each experiment, the number of agents is set at m = 25n, n being the number of arms The means of the Gaussian reward distributions on the bandit arms form a decreasing arithmetic sequence starting at µmax = µ1 = 1 and ending at µmin = µn = 0.05, so that the magnitude of the common difference is Θ( 1n ); the shared standard deviation σ = 0.1 is independent of the number of arms.

The per-agent time-averaged regret, plotted on the vertical axis, is defined as the difference between the total reward accumulated by the team over the time-horizon, divided by the number of agents and the number of epochs in the hori- Log-log plot: sigArms=0.1; #arms=40; #agents = 25*(#arms)

zon, and µ1 = 1 (this regret concept is stronger than that in Section 4). Each data-point is generated by averaging the regret values over Nsim = 105 repetitions. We set δ = 0.01, εvoi = 0.05 Nsim to ensure that our confidence bounds hold for all experiments. Figure 2 provides strong empirical evidence that, for a range of values of n and T , the VoI strategy enables a decentralized team with a sufficient number of members to achieve performance close to that with a central controller.

7 Conclusion

We formulated a novel model for the problem of reward collection by a team from multiple (stochastic) sources with costly communication, by extending the classic multi-armed bandit model to a multi-agent setting. We introduced an algorithm (decentralized softmax with VoI communication strategy) for achieving an exploration / exploitation / communication trade-off in this model. To benchmark the performance of this algorithm, we designed a centralized algorithm and proved its no-regret property. Finally, we demonstrated empirically that the performance of our decentralized algorithm, measured in terms of regret, approaches that of the centralized method. Directions of future work include evaluating our strategy under other communication cost structures, considering information acquisition costs (see, e.g., Rendell et al. [2010]), and analytically deriving the rate of convergence of our decentralized approach to the centralized benchmark.

Acknowledgments

Chakraborty and Das are grateful for support from NSF award 1560191. Juba is supported by an AFOSR Young Investigator Award.