Year: 2021

Abstract:
We consider a remote Contextual Multi-Armed Bandit (CMAB) problem, in which the decision-maker observes the context and the reward, but must communicate the actions to be taken by the agents over a rate-limited communication channel. This can model, for example, a personalized ad placement application, where the content owner observes the individual visitors to its website, and hence has the context information, but must convey the ads that must be shown to each visitor to a separate entity that manages the marketing content. In this Rate-Constrained CMAB (RC-CMAB) problem, the constraint on the communication rate between the decision-maker and the agents imposes a trade-off between the number of bits sent per agent and the acquired average reward. We are particularly interested in the scenario in which the number of agents and the number of possible actions are large, while the communication budget is limited. Consequently, it can be considered as a policy compression problem, where the distortion metric is induced by the learning objectives. We first consider the fundamental information theoretic limits of this problem by letting the number of agents go to infinity, and study the regret that can be achieved. In particular, we identify two distinct rate regions resulting in linear and sub-linear regret behaviour, respectively. Then, we propose a practical coding scheme, and provide numerical results for the achieved regret.

heading: 1 INTRODUCTION
text: In the last few years, synergies between Machine Learning (ML) and communication networks have attracted a lot of interest in the research community, thanks to the fruitful interplay of the two fields in emerging applications from Internet of things (IoT) to autonomous vehicles and other edge services. In most of these applications, both the generated data and the processing power is distributed across a network of physically distant devices, thus a reliable communication infrastructure is pivotal to run ML algorithms that can leverage the collected distributed knowledge (Park et al., 2019). To this end, a lot of recent works have tried to redesign networks and to efficiently represent information to support distributed ML applications, where the activities of data collection, processing, learning and inference are performed in different geographical locations, and should consider limited communication, memory, or processing resources, as well as addressing privacy issues.
In contrast to the insatiable growth in our desire to gather more data and intelligence, available communication resources (bandwidth and power, in particular) are highly limited, and must be shared among many different devices and applications. This requires the design of highly communicationefficient distributed learning algorithms , particularly for edge applications. Information theory, in particular the rate-distortion theory, have laid the fundamental limits of efficient data compression with the aim to reconstructing the source signal with the highest fidelity (Cover & Thomas, 2006b). However, in the aforementioned applications, the goal is often not to reconstruct the source signal, but to make some inference based on that. This requires task-oriented compression, filtering out the unnecessary information for the target application, and thus decreasing the number of bits that have to be transmitted over the communication networks. This approach should target the questions of what is the most useful information that has to be sent, and how to represent it, in order to meet the application requirements consuming the minimum amount of network resources.
Our goal in this paper is to investigate a theoretically grounded method to efficiently transmit data in a Contextual Multi-Armed Bandit (CMAB) problem, in which the context information is available to
a decision-maker, whereas the actions can be taken by a remote entity, called controller, controlling a multitude of agents. We assume that a limited communication link is available between the decisionmaker and the controller to communicate at each round the intended actions. The controller must decide on the actions to take based on the message received over the channel, while the decisionmaker observes the rewards at each round, and updates its policy accordingly.
This scenario can model, for example, a personalized ad placement application, where the content owner observes the individual visitors to its website; and hence, has the context information, but must convey the ads that must be shown to each visitor to a separate entity that manages the marketing content. This will require communicating hundreds or thousands of adds to be placed at each round, from among a large set of possible adds, within the communication resource and delay constraints of the underlying communication channel, which is quantified as the number of bits available per agent. This problem may arise in other similar applications of CMABs with communication constraints between the decision-maker and the controller (Bouneffouf & Rish, 2019).

heading: 1.1 RELATED WORK
text: Given the amount of data that is generated by machines, sensors and mobile devices, the design of distributed learning algorithms is a hot topic in the ML literature. These algorithms often impose communication constraints among agents, requiring the design of methods that would allow efficient representation of messages to be exchanged. While rate-distortion theory deals with efficient lossy transmission of signals (Cover & Thomas, 2006b), in ML applications, we typically do not need to reconstruct the underlying signal, but make some inference based on that. These applications can be modeled through distributed hypothesis testing (Berger, Sep. 1979; Ahlswede & Csiszár, 1986) and estimation (Zhang et al., 2013; Xu & Raginsky, 2017) problems under rate constraints.
In parallel to the theoretical rate-distortion analysis, significant research efforts have been invested in the design of practical data compression algorithms, focusing on specific information sources, such as JPEG and BPG for image compression, or MPEG and H.264 for video compression. While adapting these tools to specific inference tasks is difficult, recently deep learning techniques have been employed to learn task-specific compression algorithms (Torfason et al., 2018; Jankowski et al., 2021), which achieve significant efficiency by bypassing image reconstruction.
While the above mainly focus on the inference task through supervised learning, here we consider the CMAB problem. There is a growing literature on multi-agent Reinforcement Learning (RL) problems with communication links (Foerster et al., 2016; Sukhbaatar et al., 2016; Havrylov & Titov, 2017; Lazaridou et al., 2017). These papers consider a multi-agent partially observable Markov decision process (POMDP), where the agents collaborate to resolve a specific task. In addition to the usual reward signals, agents can also benefit from the available communication links to better cooperate and coordinate their actions. It is shown that communication can help overcome the inherent non-stationarity of the multi-agent environment. Our problem can be considered as a special case of this general RL formulation, where the state at each time is independent of the past states and actions. Moreover, we focus on a particular setting in which the communication is one-way, from the decision-maker that observes the state and the reward, towards the controller that takes the actions. This formulation is different from the existing results in the literature involving multi-agent Multi-Armed Bandit (MAB). In Agarwal et al. (2021), each agent can pull an arm and communicate with others. They do not consider the contextual case, and focus on a particular communication scheme, where each agent shares the index of the best arm according to its experience. Another related formulation is proposed in Hanna et al. (2021), where a pool of agents collaborate to solve a common MAB problem with a rate-constrained communication channel from the agents to the server. In this case, agents observe their rewards and upload them to the server, which in turn updates the policy used to instruct them. In Park & Faradonbeh (2021), the authors consider a partially observable CMAB scenario, where the agent has only partial information about the context. However, this paper does not consider any communication constraint, and the partial/ noisy view of the context is generated by nature. Differently from the existing literature, our goal here is to identify the fundamental information theoretic limits of learning with communication constraints in this particular scenario.

heading: 2 PROBLEM FORMULATION

heading: 2.1 CONTEXTUAL MULTI-ARMED BANDIT (CMAB) PROBLEM
text: We considerN agents, which experience independent realizations of the same CMAB problem. The CMAB is a sequential decision game in which the environment imposes a probability distribution PS over a set of contexts, or states, S, which is finite in our case. The game proceeds in rounds, and at each round t = 1, . . . , T , a realization of the state st,i ∈ S is sampled from the distribution PS for each agent i ∈ {1, . . . , N}. At each time step t, and for each agent i, states are sampled iid according to PS . In the usual CMAB setting, the decision-maker would observe the states {st,i}Ni=1 of the agents, and choose an action (or arm) at,i ∈ {1, . . . ,K} = A, for each agent, where K is the total number of available actions, with probability πt,i(at,i|st,i) given by a (possibly) stochastic policy πt : S → ∆K . Here ∆K is the K-dimensional simplex, containing all possible distributions over the set of actions. Once the actions have been taken by all the agents, at each round t the environment returns rewards for all the agents following independent realizations of the same reward process, rt,i = r(st,i, at,i) ∼ PR(r|st,i, at,i), ∀i ∈ {1, . . . , N}, which depends on the state and the action of the corresponding agent. Based on the history of returns up to round t − 1, the decision-maker can optimize its policy to maximize the sum of the rewards G = ∑T t=1 ∑N i=1 rt,i.

heading: 2.2 RATE-CONSTRAINED CMAB
text: In our modified version, the process of observing the system states is spatially separated from the process of taking the actions. The environment states, {st,i}Ni=1, are observed by a central entity, called the decision-maker, that has to communicate to the controller over a rateconstrained communication channel, at each round t, the information about the actions {at,i}Ni=1 the agents should take. The decision-maker can exploit the knowledge accumulated from the states and rewards observed by all the agents up to round t − 1, denoted by H(t − 1) ={
({s1,i}Ni=1 , {a1,i} N i=1 , {r1,i} N i=1), . . . , ({st−1,i} N i=1 , {at−1,i} N i=1 , {rt−1,i} N i=1),
} ∈ H(t−1), to
optimize the policy to be used at round t. Consequently, the problem is to communicate the action distribution, i.e., the policy πt(a|st), which depends on the specific state realizations observed in round t, to the controller within the available communication resources while inciting the minimal impact on the performance of the learning algorithm.
Specifically, the decision-maker employs function f (N)t : H(t−1)×SN → {1, 2, . . . , B} to map the history up to time t and the states of the agents at time t to a message index to be transmitted over the channel. The controller, on the other hand, employs a function g(N)t : {1, 2, . . . , B} → AN to map the received message to a set of actions for the agents. In general, both functions f (N)t and g (N) t
can be stochastic. Average per period regret achieved by sequences { f
(N) t , g (N) t }T t=1 is given by
ρ(N)(T ) = 1
T E [ T∑ t=1 N∑ i=1 r(st,i, a ∗(st,i)− r(st,i, at) ] , (1)
where at,i = gt,i(m(t)) is the action taken by agent i based on message m(t) = f (N) t ( H(t− 1), {st,i}Ni=1 ) transmitted in round t, a∗(st,i) is the action with maximum mean reward in state st,i, i.e., the optimal action, and the expectation is taken with respect to the state distribution PS and reward distribution PR. We say that, for a given time period T and N agents, an av-
erage regret- communication rate pair (ρ,R) is achievable if there exist functions { f
(N) t , g (N) t }T t=1
as defined above with rate 1N log2B ≤ R and regret ρ (N)(T ) ≤ ρ.
If a sufficiently large rate is available for communication, i.e., R ≥ logK, then the intended action for each agent can be reliably conveyed to the controller. Otherwise, to achieve the learning goal while satisfying the rate constraint, the decision-maker must apply a lossy compression scheme, such that the action distribution adopted by the pool of agents resembles the intended policy as much as possible.

heading: 3 SOLUTION
text: In this section, we present the proposed solution to the problem. First of all, we briefly discuss the algorithm adopted by the decision-maker to solve the CMAB. Then, the communication scheme for the RC-CMAB with a particular distortion function is provided, which is inherited by the learning task. We then identify two distinct rate regions resulting in linear and sub-linear regret, and propose a more practical coding scheme.

heading: 3.1 THOMPSON SAMPLING
text: In the proposed solution to the CMAB problem, the decision-maker adopts Thompson Sampling (TS) Thompson (1935). In particular, it makes use of one TS instance for each state s ∈ S . Consequently, the decision-maker maintains an estimate of the distribution ps,at (µ) of the mean reward µs,a ∈ D ⊆ R of action a in state s at time t. To take the decision in state st, the decisionmaker would sample µst,at ∼ p st,a t , ∀a ∈ A, and takes the action a∗ = arg maxa∈A{µ st,a t }. This procedure is repeated for each agent i ∈ {1, . . . , N}. After receiving the rewards {rt,i}Ni=1, the decision-maker can update its belief on µs,a, i.e., the probabilities ps,at (µ), in order to minimize the regret. We notice that this strategy induces a probability distribution πt(a|s) over the actions that is πt(a|s) = ∫ D p s,a t (µ) ∏K j=1,j 6=a P s,j t (µ)dµ, where P s,j t (µ) is the Cumulative Distribution Function (CDF) of µj , where the random variables µs,a are considered independently distributed. However, the constraint on the rate imposed by the RC-CMAB formulation makes it infeasible for the decision-maker to sample, through the pool of agents, the actions directly from the true distribution πt(a|s). The agents have to use a proxy Qt(a|s), which is the one obtained from the message received. This problem is similar to approximate TS, where a proxy distribution is used to sample the actions, or the reward means, given that the true distribution is too complex to sample from. In that case, the bottleneck is given by the complexity of the mean reward distributions, whereas in this work, it is imposed by the limited-rate communication channel between the decision-maker and the controller.

heading: 3.2 OPTIMAL SOLUTION FOR THE RC-CMAB
text: We model the environment as a Discrete Memoryless Source (DMS), that generates states from a finite alphabet S with probability PS , emitting sequences ofN symbols sN = (s1, . . . , sN ), one per agent. We then denote with Q̂sN (m) the empirical probability of state m in sN . We also consider the sequence of actions aN , and denote with Q̂zN (m, j) the empirical joint probability of the pair (m, j) in zN = ((s1, a1), . . . , (sN , aN )). The whole picture can be seen in Fig. 1. In the figure above, the actions taken by the agents are denoted by â to indicate that they can differ from a. However, we are interested in the probability distributions generating the sequences, thus we will denote with A the random variables indicating both the actions at the controller and decision-maker side. We assume that the distribution PS is known (or accurately estimated).
The decision-maker can observe the realization sN of the contexts, and its task is to transmit an index u ∈ {1, . . . , B}, and the agents can generate from u a sequence aN , such that Q̂sNaN is close to PSA(sa) = PS(s)π(a|s), where closeness depends on a distortion measure E[d(Q̂SNAN , PSA)], which in general is not an average of a per-letter distortion measure. The problem is a compression task in which the server has complete (or partial) knowledge of the states sN , and wants to transmit a conditional probability distribution πA|S to the agents, consuming the minimum amount of bits, in such a way that the empirical distributions Q̂sNaN given by the sequence induced by the agents
is close to the joint distribution PSA induced by the policy. For a distortion function d(QSA, PSA) that is 1) nonnegative, 2) upper bounded by a constant Dmax, 3) continuous in QSA, and 4) convex in QSA, in Kramer & Savari (2007), the authors provide the rate-distortion function R(D), i.e., the minimum rate R = log2 BN bits per symbol such that E[d(Q̂SNAN , PSA)] ≤ D, in the limit when N is arbitrarily large. The solution is given by
R(D) = min QA|S :d(QSA,PSA)≤D I(S;A), (2)
where QSA = PSQA|S is the joint probability induced by the environment distribution PS and policy QA|S , which depends on the information sent by the decision-maker. As we can see, in the asymptotic limit of N agents, the problem admits a single-letter solution, which also serves as a lower bound on the finite agent scenario. The studied RC-CMAB model described in Sec. 2.2 fits into this framework, and in the following section we identify an appropriate distortion function and provide its characterization.

heading: 3.3 THE KL-DIVERGENCE AS DISTORTION FUNCTION
text: When applying TS to the RC-CMAB problem with limited communication rate, the decision-maker may not be able to induce the controller to take samples from the true policy πs,at . In Phan et al. (2019), the authors provide some theoretical guidelines to construct approximate sampling policies to make the posteriors, i.e., ps,at , concentrate achieving sub-linear regret. In particular, they studied the case in which the sampling distribution Q differs from the target posterior π, using Dα(π,Q) as distortion measure, which denotes the α-divergence between the two, and is defined as
Dα(π,Q) = 1−
∫ π(x)αQ(x)1−αdx
α(1− α . (3)
In Phan et al. (2019), it is shown in Theorem 1 that, for α > 0, the condition Dα(π,Q) < δ with δ > 0, cannot guarantee that the posterior π converges in sub-linear time, even for very small values of δ. On the contrary, for α ≤ 0, the authors provide a scheme that can guarantee sub-linear regret. In particular, they suggest to introduce an exploration term ρt ∈ o(1) such that ∑∞ t=1 ρt = ∞, and the actions are sampled fromQt with probability 1−ρt, and uniformly at random with probability ρt, whileDα(πt, Qt) < δ for all t. In this case, it is possible to obtain a sub-linear regret. Consequently, in order to solve the proposed RC-CMAB problem, we decide to investigate this strategy with α = 0, which leads to the reverse KL-divergence from Q to π, or equivalently, the KL-divergence from π to Q, defined as DKL(Q, π) = ∑ x∈X Q(x) log Q(x) π(x) , when x takes values in the discrete set X . Consequently, to find the optimal constrained policy Qt(a|s), we need to find a solution to Eq. (2), which is a rate-distortion optimization problem, when the distortion function is given by the reverse KL-divergence.
We can rewrite the optimization objective of Eq. (2) as a double minimization problem (Sec. 10.8, (Cover & Thomas, 2006a))
R(D) = min Q̃(a) min QA|S :d(QSA,PSA)≤D ∑ s,a P (s)Q(a|s) log2 Q(a|s) Q̃(a) . (4)
Following (Lemma 10.8.1, (Cover & Thomas, 2006a)), the marginal Q∗(y) = ∑ x P (x)Q(y|x) has the property Q∗(y) = arg min
Q̃(y) DKL(P (x)Q(y|x)||P (x)Q̃(y)), (5)
that is, it minimizes the KL-divergence between the joint and the product P (x)Q(y), ∀Q ∈ ∆K . This means that Q̃(a) obtained by solving Eq. (4) is indeed the marginal over the actions induced by Q(a|s). Exploiting this formulation, it is possible to apply the iterative Blahut-Arimoto algorithm to solve the problem and find the solution. In particular, given that the two sets ∆K and ∆S are made of probability distributions, and the target measure is the KL-divergence, the algorithm does converge to the minimum (Csiszár & Tusnády, 1984). The process is initialized by setting a random Q̃0(a), which is used as a fixed point to compute
Q∗1(a|s) = argminQA|S :d(QSA,PSA)≤D ∑ s P (s) ∑ a Q(a|s) log2 Q(a|s) Q̃0(a) . (6)
From Q∗1(a|s), we compute the optimal Q∗1(a) by solving Eq. (5), which is simply the marginal Q∗1(a) = ∑ s P (s)Q ∗ 1(a|s). The process is iterated until convergence.
We now solve the inner minimization problem, i.e., Eq. (6) with fixed Q̃(a). As we can see, the constraint on the distortion tries to keep QA|S close to πA|S , which is the target distribution. By minimizing the mutual information, we wantQA|S as close toQA as possible, which is the marginal known by the agent (it is sent once at the beginning of the round and does not depend on the state realizations), in order to reduce the number of necessary bits to be transmitted. The solution to Eq. (2) is a conditional distribution QA|S that is a combination of the target policy conditioned on S, and the marginal distribution.
We now discuss some simple corner cases. If the maximum acceptable distortion is 0, we need QA|S = πA|S , thus the rate is equal to EPS [ DKL ( πA|S ||πA )] . If S andA are independent, i.e., the policy does not depend on the state, we have πA|S = πA, thus the decision-maker does not need to send any bits to the agents, which can just sample A ∼ πA. Moreover, if we can find a distribution QA such that EPS [ DKL ( QA||πA|S )] ≤ D, then the best strategy is not to convey any message to the controller, as the constraint is already satisfied with rate R(D) = 0. The problem is to find, among all conditional distributions Q(a|s) that satisfy the constraint, the one with the minimum divergence from Q(a), in order to minimize the rate log2 BN , i.e., the number of bits to be consumed per agent, for an arbitrarily large N , in the general case. We solve the problem using the Lagrangian multipliers, and obtain the shape of the optimal distribution given by
Qγ∗(a|s) = Q̃(a)γ ∗ P (a|s)1−γ∗∑
a′∈A Q̃(a ′)γ∗P (a′|s)1−γ∗
, ∀s ∈ S, a ∈ A, (7)
where γ∗ is s.t. EPS [DKL(Qγ∗ ||P )] = D. The derivation is provided in Appendix A.1.

heading: 3.4 ASYMPTOTIC REGRET
text: To prove the results on the achievable regret, we need additional assumptions, which are contained in the Assumption 1 in Russo (2016), which states that rewards have to be distributed following canonical exponential families, and the priors used by TS over the average rewards have to be uniformly bounded, i.e., bounded away from zero ∀(s, a). The proofs of both Lemmas are reported in the Appendix D.
In the following, we provide the minimum rate needed to achieve sub-linear regret in all states s ∈ S. We now define H(A∗) as the marginal entropy of the optimal arm, computed based on the marginal π∗(a) = ∑ s PS(s)π ∗(a|s), and defined as H(A∗) = ∑ a π ∗(a) log 1π∗(a) , and we prove that it is the minimum rate required to achieve sub-linear regret. Lemma 3.1. If R < H(A∗), then it is not possible to convey a policy Qt(s, a) that achieves sublinear regret in all states s ∈ S.
The following Lemma provides the achievibility part. Lemma 3.2. If R > H(A∗), then achieving sub-linear regret is possible in all states s ∈ S.
The consequence of this second Lemma is that, even if the exact TS policy πt cannot be transmitted ∀t, as long as sufficient rate is available, i.e., R > H(A∗), it is still possible to achieve sub-linear regret. Following the notation introduced in Sec. 2.2, this implies that, as T → ∞, and for all sub-linear regrets ρ, the regret-communication pair (ρ,R) is achievable as long as R > H(A∗). Moreover, we argue that the policy construction found in Sec. 3.3 can achieve better empirical performance w.r.t. the scheme used to prove Lemma 3.2.

heading: 3.5 PRACTICAL CODING SCHEME
text: The above analysis allows us to characterize an information theoretical bound on the optimal performance, but does not provide a constructive communication scheme. To find a practical coding scheme, we propose a solution that is based on state reduction and computes a compact state representation. In essence, the decision-maker constructs a message containing the new state representations ŝ(s) ∈ Ŝ of s, one for each agent, and send it over the channel. Once the agents have received
the message, they can sample the actions according to a common policy Qŝ(a|ŝ), which is defined on the compressed state space Ŝ. If the rate constraint imposes B bits per agent, it means that it is possible to transmit at most 2B different states to each agent. The idea is to group the states into 2B = M clusters ŝ1, . . . , ŝM , minimizing ∑ s P (s)DKL(Qŝ(a|ŝ)||π(a|s)), where Qŝ(a|ŝ) is the policy defined on the state ŝ(s) ∈ Ŝ. To find the clusters and relative policies we employ the well-known Lloyd algorithm, which is an iterative process to group states into 2B clusters. First of all, knowing the policy π, the decisionmaker maps each state si to a K-dimensional point αi = π(·|si) ∈ ∆K , finding |S| = L different points α1, . . . ,αL. Then, it generates 2B = M random points µ1, . . . ,µM ∈ ∆K as initial centroids, i.e., representative policies, and iterates over the following two steps:
1. Assign to each point αi the class j∗ ∈ {1, . . . ,M} such that j∗ = arg minj DKL(µj ||αi), i.e., minimizing the divergence between the representative µj ∗ and the original policy,
which is the point αi. For each cluster j, we now define with Sj the set containing the states associated to the policies in the cluster.
2. Update µ1, . . . ,µM such that µj = arg minµ∈∆K ∑ s∈Sj P (s)DKL(µ||π(·|s)), which
is still a convex optimization problem, and can be solved again applying the Lagrangian multipliers. The solution is
µj =
∏ s∈Sj π(·|s) P (s) A(Sj)
Z , (8)
where the product has to be considered element-wise, A (Sj) is the sum of the probabilities of states in Sj , i.e., A (Sj) = ∑ s∈Sj P (s), and Z is the normalizing factor. After computing the new centroids, we go back to step (1). The derivation of Eq. (8) is provided in Appendix A.2.
The process continues until the new solution does not decrease the KL-divergence between the clustered and the target policy DKL(Qŝ(ŝ, a)||P (s, a)) = ∑M j=1 ∑ s∈Sj P (s)DKL(µ j ||π(·|s)).
Observation Note that the controller is assumed to know the 2NR policies from which it samples the actions of the agents. This can be transmitted at the beginning of each round. In this case, the scheme is efficient as long as N log2K >> BLλ log2K, where λ is the number of bits used to represent the values of the Probability Mass Function (PMF) Qŝ(·|ŝ). For this reason, we provide a scheme where the new policy is updated not at every transmission, but just when the new target π has changed considerably. In particular, if we denote with πcls the policy defined over the compressed state representation, with πlast the last policy used to compute πcls, and with π the updated target policy, we compute and transmit πcls every time DKL(πlast||π) > β.

heading: 4 NUMERICAL RESULTS
text: In this section, we provide numerical results in support of our theoretical analysis. Additional experiments and details can be found in Appendix C

heading: 4.1 RATE-DISTORTION FUNCTION
text: In this first experiment, we analyze the rate-distortion function, and the related optimalQ(a|s), when the distortion is given by the KL-divergence in three different problems, when the numbers of states, L, and of actions, K, are both equal to 16. The target policies π(a|s) have a one-to-one relation with the states, and are generated such that π(a = i|s = j) = 0.99 if j = i, and uniformly distributed otherwise. We refer to this as the Deterministic case. In the second experiment, the target policies are generated in a similar way, but the other actions’ probabilities take random values in (0, 0.05], and then normalized. This, we call the Random Deterministic case. In the third experiment, the states are grouped in 4 blocks, such that π(a = i|s = j) = 0.99 if bj/4c = i, and uniformly distributed otherwise. This case is denoted as the Block one. In all three experiments, the distribution PS is uniform over the state space S. The rate-distortion curves are reported in Fig. 2a. As we can see, in the Deterministic case, the point with zero distortion has R(0) ∼ H(PS), where H(PS) is
the Shannon entropy of PS , as expected. Indeed, in this case, the action distributions are strongly correlated with the state, thus we need an accurate knowledge of it. In the second experiment, the starting point is similar, but the curve decreases more rapidly, caused by the random values of the other actions’ probabilities. In the third experiment, the zero distortion point is achieved atR(0) ∼ 2 bits, since, similarly to the Deterministic experiment, action probabilities are correlated with the state realization, but are grouped into four different cases. Again, given the uniform distribution over the state, R(0) ∼ H(Unif[4]), where Unif[4] is the uniform distribution over a set of 4 elements. In Fig. 2c, the approximate distributions for state s = 8 are reported for the Deterministic and Random Deterministic cases, when R = 1.

heading: 4.2 CONTEXTUAL MULTI-ARMED BANDIT
text: We now analyze the RC-CMAB problem presented in Sec. 2, and apply the clustered policy schemes to solve it. In particular, we compare the performance of the Perfect agent, which applies TS without any rate constraint, thus admits samples from the true posterior π, with the performance of the Comm, Cluster, and Marginal agents. The Comm agent uses the optimal scheme provided in Sec. 3.2, the Cluster agent implements the practical coding scheme provided in Sec. 3.5, with B = dRe bits per agent, where R is the rate adopted by the Comm agent; the Marginal agent adopts the marginal over the states, computed from the target policy π and the environment distribution PS , and serves as a lower bound on the performance. State distribution PS is uniform over L = 16 states, and there are K = 16 actions, N = 100 agents, and the total number of rounds is T = 200. The threshold for changing the clustered policy is set to β = 0.2, and the communication rate constraint to R = 2.5. In this experiment, for each state si ∈ S , the best reward is given by the arm aj such that i = j, with i, j ∈ {0, . . . , 15}. In particular, the reward behind arm i when in state j is a Bernoulli random variable with parameter µj = 0.8 if i = j, whereas µj ∼ Unif[0,0.75] if i 6= j. In this case, the best action response is strongly correlated with the state realization, thus a sufficiently high rate is required to sample from the target policy π. As it can be observed from Fig. 3(a), the theoretical rate to transmit the target policy is related to the amount of information the agent is learning from the environment, and it is computed using Eq. (2). Indeed, during the first ∼ 40 iterations, the rate is below R = 2.5. As the learning process continues, the required rate for reliable transmission increases, as the mutual information between S and A increases. We highlight that, in order to fairly represent the 16 different actions, one would need 4 bits. Indeed, another way of looking at Eq. (2) is through bottleneck principle (Igl et al., 2019), which is used to constrain the mutual information between the states and the actions, and to encourage exploration, that can be exploited to reduce the required rate when training multi-agent systems.
In Fig 3 (b), the KL-divergence between the last policy used to compute the compressed state representation, i.e., πlast in Sec. 3.5, and the target known by the decision-maker is reported. The trend shows that, at the beginning of the learning process, it oscillates rapidly, as the target policy is changing significantly between two iterations. In gray, the threshold β = 2 is highlighted, indicating when a new cluster policy has to be sent. In this experiment, the decision-maker had to send a new policy, on average, once every ∼ 7 rounds. Fig. 4 (a) reports the regret at state s = 10 (the other
plots can be seen in Appendix C.2), for the four different agents, as defined in Eq. (1). We can see that both the Cluster and the Comm agents can achieve sub-linear regret in this particular state. In Fig. 4 (b), the average rewards obtained by the agents are reported, for the different states separately. We can see that the developed scheme is still able to achieve good performance.

heading: 5 CONCLUSION
text: We have studied the RC-CMAB problem, in which an intelligent entity, i.e., the decision-maker, observes the contexts of N parallel CMAB processes, and has to decide on the actions depending on the current contexts and the past actions and rewards. However, the actions are implemented by a controller that is connected to the decision-maker through a rate-constrained communication link. First, we cast the problem into the proper information-theoretic framework, formulating it as a policy compression problem, and provided the optimal compression scheme in the limit of an infinite number of agents, when the adopted distortion measure is the KL-divergence between the compressed policy adopted by the controller and the policy of the decision-maker. We then characterize the minimum needed rate to obtain sub-linear regret, and prove that any rates above this threshold can achieve it. In the end, we designed a practical coding scheme to transmit the actions for a finite N , which relies on a compressed state representation Finally, we evaluated the performances of the policy obtained through the asymptotic information theoretic formulation, and the one obtained through the clustering scheme, and observed a close gap between the two. We numerically showed the relation between the asymptotic rate bound and the learning phase of agents, showing how it is possible to save communication resources when training a multi-agent system like the one considered. We believe that this work can serve as a first step towards understanding the fundamental performance limits of multi-agent decision-making problems under communication constraints, and highlights the intimate relation between the communication scheme and the learning process. Ongoing work include deriving an information theoretic converse result on the regret performance, and generalizing the framework to reinforcement learning problems.

heading: A POLICIES DERIVATION
text: A.1 OPTIMAL POLICY
To solve this problem, we solve the related Lagrangian
L(Q(a|s), λ, µ) = ∑ s P (s) ∑ a Q(a|s) log Q(a|s) Q̃a + λ (∑ s P (s) ∑ a Q(a|s) log Q(a|s) P (a|s) −D ) +
+ µ (∑ s P (s) ∑ a Q(a|s)− 1 ) where the Lagrangian multiplier λ has to be optimized to meet the constraints on the divergence, whereas µ ensures that the solution is a probability distributions, i.e., the elements sum up to one. The positivity constraints on the terms are already satisfied by the fact that the solution has an exponential shape. We first take the derivative of the Lagrangian w.r.t. to the terms Q(a|s) and set it to zero
∂L(Q(a|s), λ, µ) ∂Q(a|s) = P (s) log Q(a|s) Q̃(a) + P (s)− ∑ s′ Ps′Q(a|s′) P (s) Q̃(a) +
+ λP (s) ( log
Q(a|s) P (a|s) + 1
) + µP (s) = 0
finding
log Q(a|s)1+λ
Q̃(a)P (a|s)λ = −(λ+ µ)
Q(a|s)1+λ = e−(µ+λ)Q̃(a)P (a|s)λ
Q(a|s) = e −(µ+λ) 1+λ Q̃(a) 1 1+λP (a|s) λ 1+λ
and now we rewrite with γ = 11+λ , γ ∈ [0, 1], and µ such that e −(µ+λ)
1+λ is the normalizing factor. The solution has thus the shape
Qγ(a|s) = Q̃(a)γP (a|s)1−γ∑
a′∈A Q̃(a ′)γP (a′|s)1−γ
, ∀s ∈ S, a ∈ A. (9)
By the convexity of KL-Divergence and its triangular inequality, we know the solution lies on the boundary of the constraints, i.e., when EPS [DKL(Qγ∗ ||P )] = D. Consequently, if we can numerically find γ∗ s.t. EPS [DKL(Qγ∗ ||P )] = D, we solve Eq. (6).
A.2 UPDATE CENTROIDS
Again, we compute the optimal centroids by solving the Lagrangian
L(µja, λ) = ∑ s∈Sj P (s) ∑ a∈A µja log µja π(a|s) + λ (∑ a∈A µja − 1 )
taking its derivative and solving the equality
∂L(µja, λ) ∂µja = ∑ s∈Sj P (s) ( log µja π(a|s) + 1 ) + λ = 0
finding
logµjaA (Sj) = ∑ s∈Sj P (s) log π(a|s) +A (Sj) + λ
logµja = ∑ s∈Sj P (s) A (Sj) log π(a|s) + 1 + λ A (Sj)
µj =
∏ s∈Sj π(·|s) P (s) A(Sj)
Z ,
where Z is the normalizing factor, obtaining the shape expressed in Eq. (8).

heading: B PRESENTED ALGORITHMS
text: In this appendix, the algorithms for the theoretically-optimal and cluster policies are described.
B.1 THEORETICAL OPTIMAL POLICY
This is the pseudocode of the algorithm at the decision-maker side, when adopting the informationtheoretic inspired compressed policy. The only task for the controller is to decode the received message, and to communicate the actions to the agents. We define with [A] the set {1, . . . , A}, and with UnifB the uniform probability over the set B.
Algorithm 1 Optimal Policy Input rate R, n° agents N , n° actions K and state distribution PS Initialize Thompson Sampling policy π, and compressed policy Q(·|s) to Unif[K] foreach t ∈ 1, . . . , T do
Observe sNt = (st,1, . . . , st,N ) Sample aNt = (at,1, . . . , at,N ) from Q(·|s) Code aNt into ut = ft(a N t ) and transmit to the controller Observe rNt = (rt,1, . . . , rt,N ) Update action posteriors π(·|s) using the Thompson Sampling Algorithm Update Q(a|s) using the Blahut-Arimoto Algorithm (Iterate over Eq. 5 and Eq. 6)
B.2 CLUSTER POLICY
This is the pseudocode of the algorithm at the decision-maker side, when adopting the cluster policy. The task for the controller is to sample, at time t and for each agent i, the action at,i according to the last received centroid µj(st,i), whose components convey the action probabilities.
Algorithm 2 Cluster Policy Input per-agent bit B, n° agents N , n° actions K and state distribution PS , threshold β Initialize Thompson Sampling policy π Compute the centroids µj for j = 1, . . . , 2B using π with Lloyd algorithm and the rule in Eq. 8 Transmit the centroids µj to all agents. πlast = π foreach t ∈ 1, . . . , T do
Observe sNt = (st,1, . . . , st,N ) if DKL ( πlast||π ) > β then
Update the centroids µj using π with Lloyd algorithm and the rule in Eq. 8 Transmit the centroids µj to all agents.
∀st,i compute the index j(st,i) indicating its belonging cluster Transmit the vector jNt = (j(st,1), . . . , j(st,N )) Observe rNt = (rt,1, . . . , rt,N ) Update action posteriors π(·|s) using the Thompson Sampling Algorithm

heading: C EXPERIMENTS
text: In this section, additional experiments are provided to clarify the proposed scheme, and quantify the trade-offs between rate and regret.
C.1 STATE REPRESENTATION
In Fig. 5 we report the policy clustering results when applying the coding scheme explained in Sec. 3.5, when R = 2 bits can be used to represent 20 randomly generated policies. In the figure, it is possible to see the 4 policies representative of the 4 compressed state representations. As we can see, the policy centroids found by the coding scheme try to fairly resemble the shapes of all the policies within the same cluster.
C.2 DETERMINISTIC
In this section we reported some more details on the RC-CMAB experiments presented in Sec. 4.2.
C.3 8-BLOCK EXPERIMENT
In this second RC-CMAB experiment, the setting is similar to the one presented above, but the best action response is not a one-to-one mapping with the state. Again, a ∈ {0, . . . , 15} and s ∈ {0, . . . , 15}, but the Bernoulli parameter µa(s) for action a in state s is 0.8 if b s2c = a, and sampled uniformly in (0, 0.75] otherwise. Thus, the best action responses are grouped into 8 different classes, depended on the state realization. In this case, the rate is limited to R = 2.
C.4 REGRET VS NUMBER OF CLASSES
In this last experiment, the environment is the same as the one described in Sec. 4.2, a part form the number of agents, that here is N = 50. The task is to quantify the effect of the number of per-agent bits B in the cluster policy on the achievable regret, which varies from 1 to 4. As we can see from the plots below, when B is equal to 1 or 2, which in turn means that the number of clusters is, respectively, 2 and 4, the regret is not sub-linear in several states. However, the policy with just 2 bits can achieve performance comparable with the 3 and 4 bits policies in some states, e.g., state 4 and 6. This is due to the fact that even in those cases with not enough bits, the posteriors still converges to good solutions, thus if a cluster contains, for example, one state, it will convey the best policy, achieving sub-linear regret. On the contrary, when a cluster contains more states, the representative policy can fail to achieve optimal performance, if those are substantially different.

heading: D REGRET BOUND
text: To prove our statements, we define with Hq(X) and Iq(X;Y ) the marginal entropy and mutual information w.r.t. to the joint probability q, i.e.,H(A∗) = Hπ∗(A). We start by proving Lemma D.1. Lemma D.1. If the exact Thompson Sampling policies πt(a|s) achieve sub-linear Bayesian regret for all state s ∈ S, then limt→∞ Iπt(S;A) = limt→∞Hπt(A) = H(A∗).
Proof. First of all, we write Iπt(S;A) = Hπt(A)−Hπt(A|S). Following Theorem 2 from Kalkanli & Ozgur (2020), if πt(a|s) achieves sub-linear regret ∀s ∈ S, then ∀s ∈ S
lim t→∞
πt(a = a ∗|s) = 1 when a∗ is the optimal arm
lim t→∞
πt(a = a ′|s) = 0 when a′ 6= a∗.
Consequently, we have that in the limit πt(a|s) is a deterministic function, thus lim t→∞ Hπt(A ∗|S) = 0,
which concludes our proof.
Then, we prove Lemma 3.1, which is repeated below.
Lemma 3.1 If R < H(A∗), then it is not possible to convey a policy Qt(s, a) that achieves sublinear regret in all state s ∈ S.
Proof. Following Lemma 10 in Phan et al. (2019), if limt→∞ πt(a∗|s) = 1 and DKL (Qt||πt) < , ∀t, for some > 0, then limt→∞Qt(a∗|s) = 1, inducing limt→∞DKL (Qt||πt) = 0.
Now, for any policy Qt, if the minimal rate to convey it, R̂t = IQt(S;A), is below the threshold of the optimal policy, i.e., R̂t < H(A∗), by Eq. (2), we have
DKL (Qt||π∗) > 0, (10) which holds also in the limit. Otherwise, we would have a policy Qt s.t. DKL (Qt||π∗) = 0, which could be conveyed at a rate strictly below that characterized by Eq. (2), which would contradict with the definition of the rate-distortion function.
Consequently, by Lemma 10 in Phan et al. (2019) and Eq. (10), there cannot be any > 0 s.t. limt→∞DKL (Qt||πt) < ; and hence, limt→∞DKL (Qt||πt) =∞. However, if limt→∞DKL (Qt||πt) = ∞, ∃(s, a) ∈ S × A s.t. limt→∞Qt(a|s) = c > 0, when a 6= a∗. This implies that, at step t, Qt(s, a) plays a sub-optimal arm in state s with constant probability, and so it can not achieve sub-linear regret in all states.
Finally, we provide a proof for Lemma 3.2, which we repeat below.
Lemma 3.2 If R > H(A∗), then achieving sub-linear regret is possible in all states s ∈ S.
Proof. We define by Rπt the rate needed to convey the TS policy perfectly to the controller at time t, and let δ > 0 s.t. R = H(A∗) + δ, where R is the available communication rate. We now provide a scheme that guarantees sub-linear regret.
First, generate ρt parameters as in Sec. 3.3. As long as Rπt > R, with probability ρt play at uniformly at random, and with probability 1−ρt, play according to a policyQt(a|s), which satisfies the rate-distortion constraint I(A;S) < R underQt(a|s), which can be transmitted to the controller, and will have a bounded reverse KL divergence from the TS policy πt at time t. Following Lemma 14 in Russo (2016), in this way enough exploration is guaranteed for the TS policy to concentrate, and there exists a finite t0 s.t. ∀t > t0, Rπt < H(A∗) + δ. This means that, for the first t0 rounds, both the target and the approximating policies are playing sub-optimal arms with non-zero probabilities. However, their average gap is within a constant, given the average rewards are bounded within [0, 1]. Then, ∀t > t0 it is possible to play the exact TS policy, leading to the optimal policy for all future steps, and hence, a sub-linear regret.

Review summaries:
This paper studies a CMAB problem where the actions for multiple agents are sent from the decision-maker over a rate-limited communication channel. The authors developed information-theoretic performance bound for Thompson sampling based policies, which reduce the problem to transmitting conditional probability distributions over a communication channel. A practical coding method was also developed. Numerical experiments were carried out to validate the proposed design.

This work studies a rate-constrained contextual multi arm bandit (RC-CMAB) problem: the decision maker has to make action decisions for multiple parallel (independent and identical) CMAB problems (i.e. agents), but can only communicate the actions for each CMAB problem to a controller through a rate-constrained communication channel, from which the controller receives and decodes the actions of the decision maker, and applies such decoded decisions to each CMAB.  The paper first formulates the problem as a policy compression problem under an information theoretic framework, and then characterizes the optimal compression scheme for infinite agents. Next, the paper presents a practical coding scheme to communicate actions to finite agents under rate constraints, and finally benchmarks its performance against the compression scheme in the asymptotic regime.