{'fraction_non_alphanumeric': 0.03772304111714507, 'fraction_numerical': 0.009406516679596586, 'mean_word_length': 4.454906109494843, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Distributed Cooperative Decision-Making in Multiarmed Bandits

We study the explore-exploit tradeoff in distributed cooperative decision-making using the context of the multiarmed bandit (MAB) problem. For the distributed cooperative MAB problem, we design the cooperative UCB algorithm that comprises two interleaved distributed processes: (i) running consensus algorithms for estimation of rewards, and (ii) upper-confidence-bound-based heuristics for selection of arms. We rigorously analyze the performance of the cooperative UCB algorithm and characterize the influence of communication graph structure on the decision-making performance of the group.


I. INTRODUCTION
Cooperative decision-making under uncertainty is ubiquitous in natural systems as well as in engineering networks. Typically in a distributed cooperative decision-making scenario, there is assimilation of information across a network followed by decision-making based on the collective information. The result is a kind of collective intelligence, which is of fundamental interest both in terms of understanding natural systems and designing efficient engineered systems.
A fundamental feature of decision-making under uncertainty is the explore-exploit tradeoff. The explore-exploit tradeoff refers to the tension between learning and optimizing: the decision-making agent needs to learn the unknown system parameters (exploration), while maximizing its decision-making objective, which depends on the unknown parameters (exploitation).
MAB problems are canonical formulations of the exploreexploit tradeoff. In a stochastic MAB problem a set of options (arms) are given. A stochastic reward with an unknown mean is associated with each option. A player can pick only one option at a time, and the player's objective is to maximize the cumulative expected reward over a sequence of choices. In an MAB problem, the player needs to balance the tradeoff between learning the mean reward at each arm (exploration), and picking the arm with maximum mean reward (exploitation).
MAB problems are pervasive across a variety of scientific communities and have found application in diverse areas including controls and robotics [25], ecology [15], [24], psychology [22], and communications [16], [2]. Despite the prevalence of the MAB problem, the research on MAB problems has primarily focused on policies for a single agent. This research has been supported in part by ONR grant N00014-14-1-0635, ARO grant W911NF-14-1-0431, and by the Department of Defense The increasing importance of networked systems warrants the development of distributed algorithms for multiple communicating agents faced with MAB problems. In this paper, we extend a popular single-agent algorithm for the stochastic MAB problem to the distributed multiple agent setting and analyze decision-making performance as a function of the network structure.
The MAB problem has been extensively studied (see [7] for a survey). In their seminal work, Lai and Robbins [17] established a logarithmic lower bound on the expected number of times a sub-optimal arm needs to be selected by an optimal policy. In another seminal work, Auer et al. [4] developed the upper confidence bound (UCB) algorithm for the stochastic MAB problem that achieves the lower bound in [17] uniformly in time. Anantharam et al. [3] extended the results of [17] to the setting of multiple centralized players.
Recently, researchers [13], [2] have studied the MAB problem with multiple players in the decentralized setting. Primarily motivated by communication networks, these researchers assume no communication among agents and design efficient decentralized policies. Kar et al. [14] investigated the multiagent MAB problem in a leader-follower setting. They designed efficient policies for systems in which there is one major player that can access the rewards and the remaining minor players can only observe the sampling patterns of the major player. The MAB problem has also been used to perform empirical study of collaborative learning in social networks and the influence of network structure on decision-making performance of human agents [19].
Here, we use a running consensus algorithm [6] for assimilation of information, which is an extension of the classical DeGroot model [9] in the social networks literature. Running consensus and related models have been used to study learning [12] and decision-making [23] in social networks.
In the present paper we study the distributed cooperative MAB problem in which a set of agents are faced with a stochastic MAB problem and communicate their information with their neighbors in an undirected, connected communication graph. We use a set of running consensus algorithms for cooperative estimation of the mean reward at each arm, and we design an arm selection heuristic that leads to an orderoptimal performance for the group. The major contributions of this paper are as follows.
First, we employ and rigorously analyze running consensus algorithms for distributed cooperative estimation of mean reward at each arm, and we derive bounds on the estimates of mean reward at each arm and the associated variances.
Second, we propose and thoroughly analyze the cooperative UCB algorithm. We derive bounds on decision-making performance for the group and characterize the influence of the network structure on the performance.
Third, we introduce a novel graph centrality measure and numerically demonstrate that this measure captures the ordering of explore-exploit performance of each agent.
The remainder of the paper is organized as follows. In Section II we recall some preliminaries about the stochastic MAB problem and consensus algorithms. In Section III we present and analyze the cooperative estimation algorithm. We propose and analyze the cooperative UCB algorithm in Section IV. We illustrate our analytic results with numerical examples in Section V. We conclude in Section VI.

II. BACKGROUND
In this section we recall the standard MAB problem, the UCB algorithm, and some preliminaries on discrete-time consensus.

A. The Single Agent MAB Problem
Consider an N -armed bandit problem, i.e., an MAB problem with N arms. The reward associated with arm i ∈ {1, . . . , N } is a random variable with an unknown mean m i . Let the agent choose arm i(t) at time t ∈ {1, . . . , T } and receive a reward r(t). The decision-maker's objective is to choose a sequence of arms {i(t)} t∈{1,...,T } that maximizes the expected cumulative reward T t=1 m i(t) , where T is the horizon length of the sequential allocation process.
For an MAB problem, the expected regret at time t is defined by The objective of the decision-maker can be equivalently defined as minimizing the expected cumulative regret defined by is the cumulative number of times arm i has been chosen until time T and ∆ i = m i * − m i is the expected regret due to picking arm i instead of arm i * . It is known that the regret of any algorithm for an MAB problem is asymptotically lower bounded by a logarithmic function of the horizon length T [17], i.e., no algorithm can achieve an expected cumulative regret smaller than a logarithmic function of horizon length as T → ∞.
In this paper, we focus on Gaussian rewards, i.e., the reward at arm i is sampled from a Gaussian distribution with mean m i and variance σ 2 s . We assume that the variance σ 2 s is known and is the same at each arm.

B. The UCB Algorithm
A popular solution to the stochastic MAB problem is the UCB algorithm proposed in [4]. The UCB algorithm initializes by sampling each arm once, and then selects an arm with maximum where n i (t) is the number of times arm i has been chosen until time t, andμ i (t) and C i (t) = 2 ln(t) ni(t) are the empirical mean reward of arm i and the associated measure of the uncertainty associated with that mean at time t, respectively.
The function Q i (t) is judiciously designed to balance the tradeoff between explore and exploit: the termsμ i (t) and C i (t) facilitate exploitation and exploration, respectively. The UCB algorithm as described above assumes that rewards have a bounded support [0, 1] but this algorithm can be easily extended to distributions with unbounded support [18].

C. The Cooperative MAB Problem
The cooperative MAB problem is an extension of the single-agent MAB problem where M agents act over the same N arms. Agents maintain bidirectional communication, and the communication network can be modeled as an undirected graph G in which each node represents an agent and edges represent the communication between agents [8]. Let A ∈ R M ×M be the adjacency matrix associated with G and let L ∈ R M ×M be the corresponding Laplacian matrix. We assume that the graph G is connected, i.e., there exists a path between each pair of nodes.
In the cooperative setting, the objective of the group is defined as minimizing the expected cumulative group regret, defined by is the regret of agent k at time t and n k i (T ) is the total cumulative number of times arm i has been chosen by agent k until time T . In the cooperative setting using Gaussian rewards the lower bound [3] on the expected number of times a suboptimal arm i is selected by a fusion center that has access to reward for each agent is In the following, we will design a distributed algorithm that samples a suboptimal arm i within a constant factor of the above bound.

D. Discrete-Time Consensus
Consider a set of agents {1, . . . , M }, each of which maintains bi-directional communication with a set of neighboring agents. The objective of the consensus algorithms is to ensure agreement among agents on a common value. In the discrete-time consensus algorithm [11], [26], agents average their opinion with their neighbors' opinions at each time. A discrete-time consensus algorithm can be expressed as where x(t) is the vector of each agent's opinion, and P is a row stochastic matrix given by I M is the identity matrix of order M , κ ∈ (0, 1] is a step size parameter [21], d max = max{deg(i) | i ∈ {1, . . . , M }}, and deg(i) is the degree of node i. In the following, we assume without loss of generality that the eigenvalues of P are ordered such that In the context of social networks, the consensus algorithm (2) is referred to as the Degroot model [9] and has been successfully used to describe evolution of opinions [10].
One drawback of the consensus algorithm (2) is that it does not allow for incorporating new external information. This drawback can be mitigated by adding a forcing term and the resulting algorithm is called the running consensus [6]. Similar to (2), the running consensus updates the opinion at time t as where υ(t) is the information received at time t. In the running consensus update (4), each agent k collects information υ k (t) at time t, adds it to its current opinion, and then averages its updated opinion with the updated opinion of its neighbors.

III. COOPERATIVE ESTIMATION OF MEAN REWARDS
In this section we investigate the cooperative estimation of mean rewards at each arm. To this end, we propose two running consensus algorithms for each arm and analyze their performance.

A. Cooperative Estimation Algorithm
For distributed cooperative estimation of the mean reward at each arm i, we employ two running consensus algorithms: (i) for estimation of total reward provided at the arm, and (ii) for estimation of the total number of times the arm has been sampled.
Letŝ k i (t) andn k i (t) be agent k's estimate of the total reward provided at arm i per unit agent and the total number of times arm i has been selected until time t per unit agent, respectively. Usingŝ k i (t) andn k i (t) agent k can calculatê µ k i (t), the estimated empirical mean of arm i at time t defined byμ Let i k (t) be the arm sampled by agent k at time t and let ξ k i (t) = 1(i k (t) = i). 1(·) is the indicator function, here equal to 1 if i k (t) = i and 0 otherwise. Define r k i (t) = r k (t) · 1(i k (t) = i), where r k (t) is the reward of the k'th agent at time t, which is a random variable sampled from N (m i , σ 2 s ). The estimatesŝ k i (t) andn k i (t) are updated using running consensus as followŝ wheren i (t),ŝ i (t), ξ i (t), and r i (t) are vectors ofn k i (t), s k i (t), ξ k i (t), and r k i (t), k ∈ {1, . . . , M }, respectively.

B. Analysis of the Cooperative Estimation Algorithm
We now analyze the performance of the estimation algorithm defined by (5), (6) and (7). Let n cent i (t) ≡ Note that λ 1 = 1 and We also define where ν max pj = max {|ν -sum pj |, ν +sum pj } and kk indicates the k'th diagonal entry. Furthermore, let We note that both n and k c depend only on the topology of the communication graph. These are measures of distributed cooperative estimation performance.
Proposition 1 (Performance of cooperative estimation): For the distributed estimation algorithm defined in (5), (6) and (7), and a doubly stochastic matrix P defined in (3), the following statements hold (i) the estimaten k i (t) satisfies n cent i (t) − n ≤n k i (t) ≤ n cent i (t) + n ; We now bound the k-th entry of the second term on the right hand side of (10): This establishes the first statement. Using a similar approach, from (7) we can writê . This along with the definition (5) establishes the second statement.
To prove the third statement, we note that where Σ(τ ) = σ s diag(ξ i (τ )) and ν pj (τ ) = u p diag(ξ i (τ ))u j . We now examine the kk-th entry of each term in (11). We begin with the second term: We now analyze the first term of (11): Bounds in (12) and (13) along with definition (5) establish the third statement.

IV. COOPERATIVE DECISION-MAKING
In this section, we extend the UCB algorithm [4] to the distributed cooperative setting in which multiple agents can communicate with each other according to a given graph topology. Intuitively, compared to the single agent setting, in the cooperative setting each agent will be able to perform better due to communication with neighbors. However, the extent of an agent's performance advantage depends on the network structure. We compute bounds on the performance of the group in terms of the expected group cumulative regret. We also propose a metric that orders the contribution of agents to the cumulative group regret in terms of their location in the graph.

A. Cooperative UCB Algorithm
The cooperative UCB algorithm is analogous to the UCB algorithm, and uses a modified decision-making heuristic that captures the effect of the additional information an agent receives through communication with other agents as well as the rate of information propagation through the network.
The cooperative UCB algorithm is initialized by each agent sampling each arm once and proceeds as follows. At each time t, each agent k updates its cooperative estimate of the mean reward at each arm using the distributed cooperative estimation algorithm described in (5), (6), and (7). Then, at time t each agent k selects the arm with maximum and γ > 1. Note that the heuristic Q k i requires the agent k to know k c , which depends on the global graph structure. This requirement can be relaxed by replacing k c with an increasing sub-logarithmic function of time. We leave rigorous analysis of the alternative policy for future investigation.

B. Regret Analysis of the Cooperative UCB Algorithm
We now derive a bound on the expected cumulative group regret using the distributed cooperative UCB algorithm. This bound recovers the upper bound given in (1) within a constant factor. The contribution of each agent to the group regret is a function of its location in the network.
Theorem 1 (Regret of the Cooperative UCB Algorithm): For the cooperative UCB algorithm and the Gaussian multiarmed bandit problem the number of times a suboptimal arm i is selected by all agents until time T satisfies Proof: We proceed similarly to [4]. The number of times a suboptimal arm i is selected by all agents until time where η > 0 is a constant that will be chosen later.
At a given time t an individual agent k will choose a suboptimal arm only if Q k i (t) ≥ Q k i * (t). For this condition to be true at least one of the following three conditions must hold:μ We now bound the probability that (16) holds. It follows that where z is the standard Gaussian random variable and the last inequality follows from the tail bounds for the error function [1] and the second statement of Proposition 1. It follows analogously that P((17) holds) ≤ 1 2t γ . Finally, we examine the probability that (18) holds. It follows that From monotonicity of ln(t), it follows that (18) This establishes the proof.
Remark 1 (Towards Explore-Exploit Centrality): Theorem 1 provides bounds on the performance of the group as a function of the graph structure. However, the bound is dependent on the values of k c for each individual agent. In this sense, ς k ≡ 1/ k c can be thought of as a measure of node certainty in the context of explore-exploit problems. For k c = 0, the agent behaves like a centralized agent. Higher values of k c reflect behavior of an agent with sparser connectivity. Rigorous connections between k c and standard notions of network centralities [20] is an interesting open problem that we leave for future investigation.

V. NUMERICAL ILLUSTRATIONS
In this section, we elucidate our theoretical analyses from the previous sections with numerical examples. We first demonstrate that the ordering on the performance of nodes obtained through numerical simulations is identical to the ordering by our upper bounds. We then investigate the effect of connectivity on the performance of agents in random graphs.
For all simulations below we consider a 10-armed bandit problem with mean rewards as in Table I and σ s = 30. Example 1 (Regret on Fixed Graphs): Consider the set of agents communicating according to the graph in Fig. 1 and using the cooperative UCB algorithm to handle the exploreexploit tradeoff in the distributed cooperative MAB problem. The values of k c for nodes 1, 2, 3, and 4 are 2.31, 2.31, 0, and 5.43, respectively. As predicted by Remark 1, agent 3 should have the lowest regret, agents 1 and 2 should have equal and intermediate regret, and agent 4 should have the highest regret. These predictions are validated in our simulations shown in Fig. 1. The expected cumulative regret in our simulations is computed using 500 Monte-Carlo runs.
We now explore the effect of k c on the performance of an agent in an Erdös-Réyni random (ER) graph. ER graphs are a widely used class of random graphs where any two agents are connected with a given probability ρ [5].
Example 2 (Regret on Random Graphs): Consider a set of 10 agents communicating according to an ER graph and using the cooperative UCB algorithm to handle the exploreexploit tradeoff in the aforementioned MAB problem. In our simulations, we consider 100 connected ER graphs, and for each ER graph we compute the expected cumulative regret of agents using 30 Monte-Carlo simulations. We show the behavior of the expected cumulative regret of each agent as a function of ς k in Fig. 2.
It is evident that increased ς k results in a sharp increase in performance. Conversely, low ς k is indicative of very poor performance. This strong disparity is due to agents with lower ς k doing a disproportionately high amount of exploration over the network, allowing other agents to exploit. The disparity is also seen in Fig. 1, as agent 4 does considerably worse than the others. Additionally, as shown in Fig. 1 the expected cumulative regret averaged over all agents is higher than the centralized (all-to-all) case.  (10) 10 , P as in (3), and κ = dmax dmax−1 .

VI. FINAL REMARKS
Here we used the distributed multi-agent MAB problem to explore cooperative decision-making in networks. We designed the cooperative UCB algorithm that achieves logarithmic regret for the group. Additionally, we investigated the performance of individual agents in the network as a function of the graph topology. We derived a node certainty measure ς k that predicts the relative performance of the agents.
Several directions of future research are of interest. First, the arm selection heuristic designed in this paper requires some knowledge of global parameters. Relaxation of this constraint will be addressed in a future publication. Another interesting direction is to study the tradeoff between the communication and the performance. Specifically, if agents do not communicate at each time but only intermittently, then it is of interest to characterize performance as a function of the communication frequency.