{'fraction_non_alphanumeric': 0.04592510674899395, 'fraction_numerical': 0.01462230823580008, 'mean_word_length': 3.996009821976673, 'pattern_counts': {'":': 0, '<': 9, '<?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': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distributed Stochastic Bandit Learning with Context Distributions

—We study the problem of distributed stochastic multi- arm contextual bandit with unknown contexts, in which M agents work collaboratively to choose optimal actions under the coordination of a central server in order to minimize the total regret. In our model, an adversary chooses a distribution on the set of possible contexts and the agents observe only the context distribution and the exact context is unknown to the agents. Such a situation arises, for instance, when the context itself is a noisy measurement or based on a prediction mechanism as in weather forecasting or stock market prediction. Our goal is to develop a distributed algorithm that selects a sequence of optimal actions to maximize the cumulative reward. By performing a feature vector transformation and by leveraging the UCB algorithm, we propose a UCB algorithm for stochastic bandits with context distribution and prove that our algorithm achieves a regret and communications bounds of O ( d √ MT log 2 T ) and O ( M 1 . 5 d 3 ) , respectively, for linearly parametrized reward functions. We also consider a case where the agents observe the actual context after choosing the action. For this setting we presented a modiﬁed algorithm that utilizes the additional information to achieve a tighter regret bound. Finally, we validated the performance of our algorithms and compared it with other baseline approaches using extensive simulations on synthetic data and on the real world movielens dataset.


I. INTRODUCTION
Decision making under uncertain situations is a common problem in a wide range of domains including online marketing, finance, health sciences, and robotics. There exist learning algorithms that can learn good policies/strategies for optimal decision making. Contextual bandits is one such framework that models the sequential decision making process by utilizing the side information which is referred to as context [1]. In the standard contextual bandit model a learner interacts with the environment in several rounds. In each round the environment presents a context to the learner and the goal of the learner is to choose an action. Upon selecting an action the learner is presented with a reward associated with the chosen action and the goal of the learner is to maximize the cumulative reward.
The exploration-exploitation tradeoff has been widely investigated through the Multi-Armed Bandit (MAB) problem across a variety of scientific domains and has found diverse application in control and robotics [2,3,4], communications [5], and ecology [6]. In many applications using contextual bandit algorithms, including recommender systems, clinical trials, control and robotics, and cognitive radio, it is desired to learn collaboratively and concurrently in order to accelerate the learning process [7,8]. For instance, consider multiple spatially separated labs working on the same clinical trial under the orchestration of a central server. In such distributed applications, communication between agents is critical, and often communication cost is a bottleneck [8].
Another key challenge is that the contextual bandit models considered in the literature typically assume that the contexts are known. However, in many applications there are scenarios where the contexts are noisy or are forecasting measurements (e.g., weather prediction or stock market prediction), the exact contexts are unknown, and a distribution on the context is only available [9]. In such cases, the exact context is a sample from this distribution, which is hidden from the learner, and the standard algorithms for contextual bandits are not suitable.
Our goal in this paper is to develop a communication costeffective framework for distributed bandit learning with M agents when the actual contexts are unknown and only a distribution on the contexts are available to the agents. We also consider a variant of the problem, where the exact context is observed after the agents have chosen their respective actions. This setting allows us to study different applications where the contexts need to be predicted or estimated (e.g., weather conditions) at the time decision making [9], however when the reward is obtained the exact context can be measured.
Bandit learning with hidden contexts is more difficult as the learner needs to estimate the reward function from noisy observations while not knowing the exact context. To tackle this challenge we transform the problem using a feature mapping used in [9] for single agent bandit setting. After transforming the problem, we introduce a new set of feature vectors such that under this set of d-dimensional context feature vectors, the reward is an unbiased observation for the action choice. We propose a UCB-based distributed bandit algorithm with regret bound O(d √ MT log 2 (T )) for linearly parametrized reward functions and hidden contexts; the order of our regret bound matches with the regret bound of the distributed bandit algorithm in [8], where [8] considered the exact contexts are known. Further, our setting recovers the distributed bandit algorithm with known contexts in [8] when the context distribution is a Dirac delta distribution.
We note that a straightforward communication protocol for distributed bandit learning is immediate sharing where each agent shares every new sample immediately with the other agents as noted in [8]. While the agents can achieve near optimal regret under this protocol, the amount of communication data is directly proportional to the total size of collected samples, which makes the problem not scalable for large time horizons. To minimize the communication cost while maintaining optimal regret, we utilize the observation in [10] and perform synchronization between agents only when the additional information available to the agents is significant when compared to the last synchronization.  [8] the exact context is known and for the two settings considered in this paper (i) only the context distribution is available and (ii) the context is unknown while choosing the action and is observed when the rewards are received. The orders of the regret bounds for settings (i) and (ii) matches with the baseline setting and hence ours is a tight bound. We note that while the order of the regret bounds for Algorithms 1 and 2 (i.e., settings (i) and (ii)) are the same we explain in Section V how to achieve a tighter bound for (ii) using the confidence set scaling. Also, in immediate sharing the agents share their information at the end of every round, and hence the communication cost is higher than our setting.

Setting
Algorithm This paper makes the following contributions. A summary of our regret and communication bounds is given in Table I. • We model a distributed stochastic linear contextual bandit formulation when an adversary chooses a distribution on the set of possible contexts and a set of M agents work collaboratively to minimize their total regret under the coordination of a central server. • We present a UCB-based algorithm that achieves a O(d √ MT log 2 T ) high probability regret bound for distributed stochastic bandits with linear parametrized reward function when only the context distribution is available and the exact context is hidden.
• We consider a variant of the problem where the context is not observed while selecting the action and is observed after receiving the reward. For this setting, we present a modified algorithm that can achieve a tighter regret bound utilizing the additional information. • We validated the performance of our approach and compared the different models via numerical simulations on synthetic data and on the real world movielens data. The rest of the paper is organized as follows. In Section II we present the notations and the problem formulation. In Section III we present the related work. In Section IV we present the algorithm and regret analysis for the stochastic bandit problem with context distribution. In Section V we present the algorithm and regret analysis for the setting where the actual context is observed after choosing the action. In Section VI we present the simulation results and in Section VII we present the conclusion.

A. Notations
The norm of a vector z ∈ R d with respect to a matrix V ∈ R d×d is defined as z V := √ z V z and |z| for a vector z denotes element-wise absolute values. Further, denotes matrix or vector transpose and ·, · denotes inner product. For an integer N, we define [N] := {1, 2, . . . , N}.

B. Problem Setting: Distributed Linear Stochastic Bandits with Context Distribution
In this section, we first specify the standard linear bandit problem below and then explain the distributed stochastic bandit setting studied in this paper. Let X be the action set, C be the context set, and the environment is defined by a fixed and unknown reward function y : X × C → R. In linear bandit setting, at any time t ∈ N, the agent observes a context c t ∈ C and has to choose an action x t ∈ X . Each context-action pair (x, c), x ∈ X and c ∈ C, is associated with a feature vector φ x,c ∈ R d , i.e., φ x t ,c t = φ (x t , c t ). Upon selection of an action x t , the agent observes a reward y t ∈ R where θ ∈ R d is the unknown reward parameter, θ , φ x t ,c t = r(x t , c t ) is the expected reward for action x t at time t, i.e., r(x t , c t ) = E[y t ], and η t is σ −Gaussian, additive noise. The goal is to choose optimal actions x t for all t ∈ T such that the cumulative reward, ∑ T t=1 y t , is maximized. This is equivalent to minimizing the cumulative (pseudo)-regret denoted as Here x t is the optimal/best action for context c t and x t is the action chosen by the agent for context c t . In this work, we consider a distributed stochastic linear bandit setting with context distribution and unknown contexts. The communication network consists of a server and a set of M agents, and the agents can communicate with the server by sending and receiving packets. We assume that the communication between the server and the agents have zero latency. We consider a setting where the context at time t, c t is unobservable rather only a distribution of the context denoted as µ t is observed by the agents. At round t, the environment chooses a distribution µ t ∈ P(C) over the context set and samples a context realization c t ∼ µ t . The agents observe only µ t and not c t and each agent selects an action, say action chosen by agent i is x t,i , and receive reward y t,i , where y t,i = θ , φ x t,i ,c t + η t,i . Our aim is to learn an optimal mapping/policy P(C) → X of contexts to actions such that the cumulative reward, ∑ M i=1 ∑ T t=1 y t,i is maximized. Formally, our aim is to minimize the cumulative regret Here, x t = arg max x∈X E c∼µ t [r x,c ] is the best action provided we know µ t , but not c t , and T is the total number of rounds. Consider the set I = {(1, 2, · · · , T ) × (1, 2, · · · , M)} = {I 1 , I 2 , . . . , I MT }, which is the set of all possible (t, i) pairs for t ∈ [T ] and i ∈ [M]. For I j−1 = (t, i) ∈ I, we have i = j − 1 mod M, t = j − 1/M , and we define F j−1 := (x s,q , µ s , y s,q ) {(s,q):(s<t)∨(s=t∧q<i)} . We note that in (3), we compete with the best possible mapping π : P(C) → X from the observed context distribution to actions, that maximizes the expected reward where F j−1 is the filtration that contains all information available at the end of round j − 1.
Our goal is to develop a distributed multi-armed bandit algorithm with the least possible communication cost to solve this problem. We define the communication cost of a protocol as the number of integers or real numbers communicated between the server and the agents [8]. We make the standard assumptions on the additive noise η t and the unknown parameter θ [9,11].

III. RELATED WORK
Multi-Armed Bandits (MAB): MAB algorithms are well studied [12,13,14] and different solution approaches have been proposed, for a survey see [1] and [15]. The bandit setting that is closely related to this paper is the stochastic contextual bandits, where the learner chooses actions after observing the contexts and the goal is to learn an optimal mapping from contexts to actions. The fundamental difference between stochastic contextual bandits and Reinforcement Learning (RL) [16] is that the sequence of contexts can be arbitrary and even chosen by an adversary unlike in an RL setting which has a specific transition structure. Linear contextual bandits is a popular variant of the contextual bandits and it has been studied in [10,17,18,19,20,21,22] and strong theoretical guarantees are established using different solution approaches. A prominent approach is the Upper Confidence Bound (UCB) algorithm [19,23] which was later improved in [10,18,24] with stronger guarantees. Another solution approach is using Thompson sampling and algorithms with theoretical guarantees are provided in [21]. In the linear contextual bandit setting, the context in round t is known and hence it is a special case of the bandit setting considered in this paper with the choice of the distribution µ t as a Dirac delta distribution denoted as µ t = δ c t for all t ∈ T . Linear contextual bandits with uncertainty in the context is studied in [9,25,26]. [26] considered a setting where the contexts are perturbed by noise and the goal is to compete with the optimal policy that has access to the unperturbed feature vector. On the other hand, [9] considered a setting in which the context itself is not observable rather a distribution on the context is available and the goal is to choose a best action as a function of the distribution. In this paper we built on the work in [9] to address a multi-agent stochastic contextual MAB problem with hidden context. We reduce the multi-agent problem into a distributed linear contextual bandit setting with action-dependent noise. Such a bandit model is referred to as heteroscedastic bandits. Heteroscedastic bandits with linear reward structure has been studied in [27,28]. The key difference between the existing works on heteroscedastic bandits and our work is that we consider a multi-agent distributed MAB setting rather than a single agent setting.
Distributed bandits: Recently, MAB with multiple players have attracted increased attention [29]. Our model is closely related to the distributed bandits considered in [8], where the agents face the same bandit model, and the agents communicate with a central server by sending and receiving information in order to learn in a collaborative and concurrent manner. It considered two settings and proposed two algorithms DELB and DisLinUCB, for fixed and time varying action sets, respectively. The time-varying action set setting is similar to our setting, however, the key difference is that in [8] the contexts are known to the agents while we consider a setting where contexts are hidden from the agents.
Distributed MABs are considered in a setting with collisions where the reward for an arm decreases or is set to zero if that action is chosen by a player in [5,30,31,32]. A follow-up work of [31], [33] considered a setting in which the regret increases when the agents communicate. A collision-based model is relevant to problems in cognitive radio networks, where the goal is to learn from action collisions rather than through communication. This is fundamentally different from the setting considered in our work.
Decentralized bandits: A decentralized MAB model with fixed action set was considered in [35,36,37], where the agents share their estimates with their neighbors over an undirected communication network. A similar setting was considered in [38] where in each round an agent can communicate with a few random neighbors. [39] considered a setting where at each round an agent can communicate with exactly one neighbor. On the other hand, [40,41] studied the problem of identifying an εoptimal arm using a distributed network and provided matching upper and lower bounds when communication happens only once and when the graph topology is restricted to be the complete graph. The communication and information sharing between agents in [35,36,37,38,39,40,41] is different from the communication model that of this paper. Further, [35,36,37,38,40,41] considered a model with fixed action set, while we consider a setting with time-varying action set. To the best of our knowledge, this is the first work that consider a distributed multi-agent contextual MAB with hidden contexts.

IV. DISTRIBUTED UCB FOR LINEAR STOCHASTIC BANDITS WITH CONTEXT DISTRIBUTION A. Proposed Algorithm and Guarantee
In this section, we present the algorithm for solving the distributed stochastic contextual bandit when the actual context is not observable rather a distribution is only available (e.g., weather prediction/forecast, stock market prediction). Our solution approach is built on the works of [8] and [9]. The pseudocode of our algorithm is presented in Algorithm 1.
Given the distribution µ t , we construct the feature vectors c ]} is the expected feature vector of action x under µ t . We note that, each feature ψ x,µ t corresponds to exactly one action x ∈ X and we use Ψ t as the feature context set at time t. Our algorithm is based on the optimism in the face of uncertainty principle, where at each time t ∈ [T ], each agent i ∈ [M] maintains a confidence set B t,i ⊆ R d that contains the unknown parameter vector θ with high probability. Each agent then chooses an optimistic estimateθ t, and chooses an action x t,i = arg max x∈X ψ x,µ tθ t,i . Equivalently the agent chooses the pair (x t,i ,θ t,i ) ∈ arg max (x,θ )∈X ×B t,i ψ x,µ t θ which jointly maximizes the reward. The agents now play their respective optimistic action, x t,i , and receive rewards y t,i 's and utilize the reward observations to update their individual confidence set. We note that it is not immediately clear how this is feasible since y t,i is a noisy observation of φ x t,i ,c t θ and the algorithm expects the reward ψ x t,i ,µ t θ . To address this, we construct a feature set Ψ t in such a way that y t,i is an unbiased observation for the action choice ψ t , similar to the technique in [9] for single agent bandits. We as W t,i and U t,i , respectively. We construct the confidence set B t,i using W t,i and U t,i as i . Without synchronization, agents in our protocol execute Algorithm 1 in [9] separately. In that case the regret will be scaled by a factor M. During synchronization agents share all newly acquired samples with each other. The synchronizations are done at specific time instants. We refer to the timesteps between the two synchronizations as epochs. The epochs are designed based on the observation in [10] that the change in the determinant of V t is a good indicator of learning progress. Based on this observation, we only synchronize when agent i finds that the log-determinant of V t,i has changed more than a constant factor since the last synchronization, and this reduces the communication cost of the algorithm. The pseudocode of our algorithm is described below.
We now present the regret and communication bound for Algorithm 1.
Theorem 4.1. The cumulative regret of Algorithm 1 with expected feature set Ψ t and β t,i = β t,i ( √ 4 + σ 2 , δ /2) is bounded at time T with probability at least 1 − Mδ by Further, for δ = 1 M 2 T , Algorithm 1 achieves a regret of Proof. See Section IV-B.

B. Regret Analysis
Proof of Theorem 4.1 relies on the four main results we present below. The first lemma proves that θ lies in the constructed confidence set with a certain probability.
for Agent i = 1, 2, . . . , M, do 7: Construct the confidence ellipsoid B t,i using V t,i andθ t,i 9: Send a synchronization signal to server to start a communication round 15: end if 16: Synchronization round: 17: if a communication round is started then 18: All agents i ∈ [M] send W t,i and U t,i to server 19: All agents receive W syn ,U syn from the server 21: Set W t,i = 0,U t,i = 0,t last = t, for all i, V last = λ I +W syn Further, if X t 2 L for all t, then Consider an arbitrary epoch in Algorithm 1, say the p th epoch. Let E p be the set of all (t, i) pairs in epoch p and V p be the V last in epoch p. Then we know All the epochs that satisfy (5) are referred to as the good epochs. Similarly, all the epochs that do not satisfy (5) are referred to as the bad epochs. Our approach to prove Theorem 4.1 is to prove bounds for good epochs and bad epochs separately as described below. Let us denote the number of timesteps that belong to good epochs as T g and the number of timesteps that belong to bad epochs as T b . Let us denote the cumulative regret in all good epochs until time T as R g (T ) and the cumulative regret in all bad epochs until time T as R b (T ). Below we present the bounds for R g (T ) and R b (T ). Proof. See Section IV-C.
Theorem 4.5. The cumulative regret of all bad epochs in Algorithm 1 with expected feature set Ψ t and β t,i = β t,i ( Proof. See Section IV-C.
We now present the proof of Theorem 4.1.
Proof of Theorem 4.1. Set δ = 1/ M 2 T . Then the expected regret caused by the failure of the condition given in Lemma 4.2 is at most Mδ · MT · 1 = M · 1 M 2 T · MT · 1 = O(1). To this end, we mainly consider the case where the condition in Lemma 4.2 holds.
Let us choose B = ( T log MT dM ), then The last step uses β T = O d log( T δ ) . Since T > M, we have MT log 2 (T )).

Communication:
The communication cost for our algorithm follows the approach in [8]. We present it here for completeness. Recall R = O(d log(MT )). Let α = BT R . This implies that there could be at most T /α = T R B epochs that contains more than α time steps. Consider epochs p and p + 1. If the p-th epoch contains less than α time steps, we get Further,

As a result, there could be at most
epochs with less than α time steps. Therefore, the total number of epochs is at most

C. Proofs of Theorem 4.4 and Theorem 4.5
We first present lemmas that are used in the proofs of Theorem 4.4 and Theorem 4.5, and then present the proofs. Recall F j−1 = (x s,q , µ s , y s,q ) {(s,q):(s<t)∨(s=t∧q<i)} , the information available at the end of round j − 1. Define Below we prove that D j−1 is a martingale difference sequence.
Lemma 4.6. D j is a martingale difference sequence with D j 4 and ∑ j D j is a martingale.
F j−1 = (x s,q , µ s , y s,q ) {(s,q):(s<t)∨(s=t∧q<i)} . Thus we have = 0 Eq. (7) follows from ψ x t,i ,µ t = E c t ∼µ t φ x t,i ,c t | F j−1 , µ t , x t,i . Therefore D j is a martingale difference sequence with D j 4 and ∑ MT j=1 D j is a martingale. The Azuma-Hoeffdings inequality given in Proposition 4.7 bounds martingale sequence.
Using Proposition 4.7 we bound D j below. Lemma below proves a bound on the per-step regret of Algorithm 1. Lemma 4.9. In Algorithm 1, with probability 1 − δ , the single step pseudo-regret r t, Proof. Let us assume that θ ∈ B t,i . Then we have Eq. (8) holds since θ t,i , ψ x t,i ,µ t is the optimistic solution obtained in Algorithm 1 (line 9). Eq. (9) uses the linear algebra result that for any vector z, Eq. (10) uses the result XY V X V + Y V and (11) (12) follows from Lemma 4.2 with λ = 1 which we explain below.
We note that Lemma 4.2 cannnot be directly applied in (12) since the reward observation y t,i = φ x t,i ,c t θ + η t is generated from a different feature vector than the features ψ x t,i ,µ t used for learning in Algorithm 1. However, we can rewrite We know E[ζ t |F j−1 , µ t , x t,i ] θ = 0. Since ζ t depends on x t,i , ζ t is heteroscedastic. However, since |ζ t | 2, it is 2-subGaussian. Thus we can use the homoscedastic noise bound and y t,i is a noisy observation of y t,i = ψ x t,i ,µ t θ with √ 4 + σ 2 -subGaussian noise, since for two independent random variables X and Y that are σ 1 and σ 2 sub-Gaussian, X +Y is σ 2 1 + σ 2 2 sub-Gaussian. Thus the construction of the confidence set for the least squares estimator using ψ x t,i ,µ t remains valid with ρ = √ 4 + σ 2 . Thus (12) follows with β t,i = β t,i ( Now we present the proof of Theorem 4.4 which uses the per-step regret bound obtained in Lemma 4.9 and the bound on D j obtained in Lemma 4.8. Our approach also uses similar argument in Theorem 4 in [10]. Proof of Theorem 4.4. Assume that the MT pulls are all made by one agent in a round-robin fashion (i.e., the agent takes x 1,1 , x 1,2 , . . . , x 1,M , x 2,1 , . . . , x 2,M , . . . , x T,1 , . . . , x T,M ). We define V t,i := λ I + ∑ {(s,q):(s<t)∨(s=t∧q<i)} x s,q x s,q . Thus V t,i denotes V t,i the imaginary agent calculates when the agent gets to x t,i . Since x t,i is in a good epoch (say the p-th epoch), we get Eq. (13) uses det(V t,i ) det(V p−1 ) and the fact that for good epochs det( V t,i ) = det(V p ). From Lemma 4.9 we have w.p 1−δ The last three steps follow from Lemma 12 in [10] by which x Ax x Bx det(A) det(B) and (13). We now use the argument for the single agent regret bound and prove regret bound for the good epochs. Let E p be the set of (t, i) pairs that belong to epoch p, and P g be the set of good epochs. Let A g ⊆ [MT ] be the set of all j ∈ [MT ] that belong to good epochs. That is, j ∈ A g if I j = (t, i) and (t, i) ∈ E p where p ∈ P g . Using Proposition 4.3, In the inequalities above, (15) (18) follows from Proposition 4.3. Finally, suppose that there are P epochs, then V P will be the matrix with all samples included. We have det Then (19) follows after substituting Using Lemma 4.8 with n = MT g and after applying a union bound, we can rewrite (19) as below with β t,i = β t,i ( Using the per-step regret bound obtained in Lemma 4.9 we now prove Theorem 4.5 which presents the regret bound for the bad epochs.
Proof of Theorem 4.5. Let p be a bad epoch. Suppose that at the start of each bad epoch, we have V last . Assume that a bad epoch starts at time step t 0 and that the length of the epoch is n. Then agent i proceeds as V t 0 ,i , . . . ,V t 0 +n,i . Using Lemma 4.9 regret in this epoch, denoted as R p , satisfies The last four inequalities follow from t−1,i , Proposition 4.3, and the fact that all the agents in the bad epochs satisfy n log(det(V t 0 +n,i )/det(V last )) < B. We note that β T = max i β T,i . Since we have the bound on regret for a bad epoch, we now proceed to bound the number of bad epochs to get the cumulative bound on the bad epochs. Recall Thus the number of bad epochs is at most R. Using Lemma 4.8 with n = MT b and after applying a union bound, we can rewrite (20) as below with β t,i = β t,i (

A. Proposed Algorithm and Guarantee
In this section, we present our algorithm and regret bound for the setting where the actual context c t (e.g., actual weather measurements) is observable to the agents after they choose their actions. We note that, in Algorithm 1, each agent i ∈ [M] only uses the information {(x s,i , µ s , y s,i )} t s=1 for estimatingθ t,i . However, with the context observation the agents have {(x s,i , c s , y s,i )} t s=1 available to them while estimatingθ t,i although not for selecting the action. To this end, we modify our algorithm to utilize this information, to obtain a tighter regret bound, similar to the approach in [9]. The fundamental difference of our approach and that of [9] is that we consider a multi-agent distributed bandit setting, while [9] considered a single agent bandit setting. The difference with respect to Algorithm 1 is that we update W t,i and U t,i as A simplified pseudocode is given in Algorithm 2. For a full code refer to Algorithm 1 with line 11 replaced by (21). Nature chooses µ t ∈ P(C)

5:
for Agent i = 1, 2, . . . , M, do 6: Construct the confidence ellipsoid B t,i using W t,i andθ t,i = V −1 t,i U t,i , where V t,i = λ I +W t,i 8: Play x t,i and get the reward y t,i 10: Update W t,i and U t,i
The significance of Theorem 5.10 is that it allows us to use a smaller scaling β t,i for the confidence set, which indeed affects the action chosen by the algorithm. It is known that in practice β t,i has a large impact on the amount of the exploration, and a tighter choice of β t,i can result in a significant reduction of the regret bound [9], which we validate through the experiments.

B. Regret Analysis
Proof of Theorem 5.10 relies on Lemma 4.2, Proposition 4.3, and the two main results we present below, Theorems 5.11 and 5.12.
Theorem 5.11. The cumulative regret of all good epochs in Algorithm 2 with expected feature set Ψ t and β t,i = β t,i (σ , δ /3) is bounded at time T with probability at least 1 − Mδ by Proof. See Section V-C.
Theorem 5.12. The cumulative regret of all bad epochs in Algorithm 2 with expected feature set Ψ t and β t,i = β t,i (σ , δ /3) is bounded at time T with probability at least 1 − Mδ by Proof. See Section V-C.
Proof of Theorem 5.10. Using Theorem 5.11 and Theorem 5.12 and following similar steps as in the proof of Theorem 4.1 along with B = ( T log MT dM ) and T > M we get Let us choose B = ( T log MT dM ), then

The last step uses
The bound on the communication cost follows the same step as in Below we prove ∑ j∈[MT ] S j is a supermartingale.
Using proposition 4.7, we provide below a bound on ∑ j∈[MT ] S j .
Lemma 5.14. The supermartingale ∑ j S j is bounded with probability at least 1 − δ as Proof. From Lemma 5.13 we know that S j is a supermartingale with S j 2λ −1/2 . Now from Proposition 4.7 we have ∑ j S j 2λ −1/2 2n log 1 δ .
The lemma below proves a bound on the per-step regret of the protocol.
Below we present the proof of Theorem 5.11. It follows a similar approach to the proof of Theorem 4.4 and uses Lemma 5.15 and Lemma 5.14. M = 1, 3, 5 and compared the results as shown in Fig. 1b. We ran for 1000 time-period and 100 independent trails. Movielens data: We used the movielens-1m dataset movielens-1m dataset [42]. The data consists of the movie ratings and the demographic information of the users. In the interactive setting, the context corresponds to a randomly chosen user from the data. We first used Singular Value Decomposition (SVD) to learn 6-dimensional feature vectors v u , w m for the users u and the movies m, respectively, and then obtained the linear parameters φ as φ m,u = v u w m which has 36-dimensions. We constructed ψ as ψ m,u = n u w m , where n u is obtained after adding noise to v u , i.e., the details of the user is not accurately known. This completed the preprocessing steps on the realworld movielens dataset to obtain a benchmark for evaluating the performance our algorithms.
We present the plots showing variation of the cumulative regret with respect to the execution time for the movielens data for different settings and for different number of agents in Figure 2. The reward r(x t , c t ) is bounded above by 1 and the observation noise η t is set as Gaussian with zero mean and standard deviation 10 −3 . In this experiment, as expected, the variant that does not observe the context (hidden) is outperformed by the variant that uses the context observation for the estimation but not while choosing the actions (observed) as shown in Fig. 2a. We varied the number of agents as M = 1, 3, 5 and ran for a time-period of T = 1000 and the plots are shown in Fig. 2b.

VII. CONCLUSION
In this work, we studied distributed stochastic multi-arm contextual bandit problem with unknown contexts. In our distributed setting, M agents work collaboratively to choose optimal actions under the orchestration of a central server in order to minimize the total cumulative regret when the agents only observe the context distribution and the exact contexts are hidden. Based on feature vector transformation, we proposed a UCB-based algorithm and proved regret and communications bounds of O(d √ MT log 2 T ) and O(M 1.5 d 3 ), respectively, for linearly parametrized reward functions. We extended the problem setting to a case where the agents observe the actual context after choosing the action. For this setting we present a modified algorithm so that we can achieve a tighter regret bound using the additional information. To validate the performance of our approach we perform extensive simulations on synthetic data and on movielens data set. As a part of our future work, we plan investigate the fully-decentralized setting of the problem in which there will be no central server and the agents are allowed to communicate with their neighboring agents defined by a communication network.
Suppose event A = θ lies in B t,i , P(A) 1 − δ and P A δ . By the union bound, we know P(