Contextual Multi-Armed Bandit with Communication Constraints
Authors: Francesco Pase
Deniz Gunduz
Michele Zorzi
Venue: ICLR 2022 Submitted (2022)
Keywords: Machine Learning
Information Theory
Multi-Armed Bandits

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. Then, we propose a practical coding scheme, and provide numerical results for the achieved regret.

Under review as a conference paper at ICLR 2022
CONTEXTUAL MULTI-ARMED BANDITS WITH COMMUNICATION CONSTRAINTS
Anonymous authors Paper under double-blind review
ABSTRACT
We consider a remote Contextual Multi-Armed Bandit (CMAB) problem, in which the poccision-makee observes the context and the reward, but must communi- cate the actions to be taken by the agents over a rate- ente-limited communication chan- nel. 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 shown to each visitor separate entity that manages the marketing content. In this Cate-Constrained CMAB (RC-CMAB) problem, the constraint on the communication rate between the decision-make and the agents imposes 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 consid- ered as a policy compression problem, where the distortion metric 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.
INTRODUCTION
In the last few years, synergies between Machine Learning (MI.) 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 ser- vices. In most of these applications, both the generated data and the processing power is distributed across network of physically distant devices, thus reliable communication infrastructure is piv- otal to run ML algorithms that can leverage the collected distributed knowledge (Park et al., 2019). To this end, lot of recent works have tried to redesign networks and to efficiently represent infor- mation to support distributed ML applications, where the activities of data collection, processing, learning and inference 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 gather more data and intelligence, available com- munication 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 communication- efficient 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 often not to reconstruct the source signal, but make some inference based 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 Contextual Multi-Armed Bandit (CMAB) problem, in which the context information is available to

---

Under review as a conference paper at ICLR 2022
decision- whereas the actions can be taken by remote entity, called controller, controlling multitude of agents. We assume that a limited communication link is available between the decision- maker and the controller to communicate each round the intended actions. The controller must decide on the actions to take based on the message received over the channel, while the decision- maker 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 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 mar- keting content. This will require communicating hundreds or thousands of adds to be placed at each round, from among large set of possible adds, within the communication resource and de- lay constraints of the underlying communication channel, which quantified as the number of bits available per agent. This problem may arise in other similar applications of CMABs with commu- nication constraints between the decision-man maker and the controller (Bouneftouf & Rish 2019).
1.1
RELATED WORK
Given the amount of data that is generated by machines, sensors and mobile devices, the design of distributed learning algorithms is 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 (006b)) in ML applications, we typically do not need to reconstruct the underlying signal, but make some inference based that. These applications can be modeled through distributed hypothesis testing (Berger Sep. 1979; Ahlswede & Csiszár, 1986) and estimation (Zhang et al.) 2013 Xu & Raginsky 2017) problems under rate constraints.
In parallel to the thcoretical 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 con- sider 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 al., 2017). These papers consider a multi-agent partially observable Markov decision process (POMDP), where the agents collaborate to resolve a specific task. In ad- dition 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 -tatstationarttyy of the multi-agent environment. Our problem can be considered as special case of this general RL formulation, where the state 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 al. (2021). each agent can pull an arm and communicate with others. They do not consider the contextual case, and focus on a particular com- munication scheme. where each agent shares the index of the best arm according to its experience. Another related formulation is proposed in Hanna et al.] (202I), 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 par- tially 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 thcoretic limits of learning with communication constraints in this partieular scenario.
2

---

Under review as a conference paper at ICLR 2022
2 PROBLEM FORMULATION
2.1 CONTEXTUAL MULTI-ARMED BANDIT (CMAB) PROBLEM
We consider N 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 set of contexts, or states, S, which is finite in our case. The game proceeds in rounds, and a realization of the state 8t, E S is sampled from the distribution Ps for each agent i E (1, (1..... N). At each time step I, and for each agent é, states are sampled iid according to Ps. In the usual CMAB setting, the decision agents, and choose an action (or arm) d4 {I...., K} = A. for each agent, where K is the total number of available actions, with probability Te.s (a..(ar, given by a (possibly) stochastic policy T, S Ax. Here AK 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 & the environment returns rewards for all the agents following independent realizations of the same reward process, re,i = r(St, (t,;) (R(r|sr, at,)) Vi E {l..... N}, which depends on the state and the action the decision-maker can optimize its policy to maximize the sum of the rewards = Σ En Pt.5
at each round f = 1, .....,7 T,
would observe the states { of the
of the corresponding agent. Based on the history of returns up round
2.2 COTE-CONSTRAINED CMAB
In modified version, the process of observing the system states is spatially separated from the process of taking the actions. The environment states, {s are observed by cen- tral entity, called the decision- constrained communication channel, at each round t, the information about the actions {a the agents should take. The decision-makee states and rewards observed by all the agents up to round t 1, denoted by H - 1) { ((a1,))) (ar (ri.)) ..., (1
N
that has to communicate to the controller over a rate-
can exploit the knowledge accumulated from the
N ( 1,)e-,,;)=)) N (re-1))) } H(--1), to
optimize the policy to be used at round t. Consequently, the problem is to communicate the ac- tion distribution, i.e., the policy T. (.)ss),, which depends the specifie state realizations observed in round f, to the controller within the available communication resources while inciting the minimal impact the performance of the learning algorithm.
Specifically, the decision-maker employs function y! (((--)) x SN + 21,2,.... .y......))) B} to map the history up to time t and the states of the agents at time / to message index to be transmitted over the channel. The controller, on the other hand, employs function 9; (,N) 21. B) - A to
map the received message to set of actions for the agents. In general, both functions S (((N) and gt (N)
can be stochastic. Average per period regret achieved by sequences [ 99. t=1
(N))
is given by
T
N
r ("e.)) r r(52,1, ae)
(T))
E
(1)
|=
where at, = (m(()) is the action taken by agent i based on message m(() ((N) (H(1-1), (,,,))))) transmitted in round I, a (*1,)) is the action with maximum mean re- ward in state St,s, i.e., the optimal action, and the expectation is taken with respect to the state distri- bution Ps and reward distribution PR. We say that, for a given time period T and N agents, an av- (N))
erage regret- communication rate pair (p, R) is achievable if there exist functions { (1()) .6 Jtz
as defined above with rate 1/4 log, B S R and regret (N) (T') < p.
If a sufficiently large rate is available for communication, i.e., R > log K, 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-male maker must apply lossy compression scheme, such that the action distribution adopted by the pool of agents resembles the intended policy as much possible.
3

---

Under review as a conference paper at ICLR 2022
4
4
Encoder
P
Q(als)
Figure 1: The problem of communicating policies.
SOLUTION
In this section, 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 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 more practical coding scheme.
3.1 THOMPSON SAMPLING
In the proposed solution to the CMAB problem, the decision-maker adopts Thompson Sampling (TS) Thompson (1935). In particular, makes use of one TS instance for each state s E S. Con- sequently, the decision-make maintains
estimate of the distribution p; (H) of the mean reward 11000 E D S R of action a in state s at time t. To take the decision in state St, the decision- maker would sample p. nr Pt ft.a Va A, and takes the action a" arg max ( This procedure repeated for each agent E [N)...,N.. After receiving the rewards {re,)]= the decision-maker can update its belief on 14* i.e., the probabilities p; (w), in order to minimize the regret. We notice that this strategy induces probability distribution (T(aas) over the actions that Te (a(as) P
" I5=1,44 (w)du, where pe (p) is the Cumulative Distribution Function (CDF) of μj. where the random variables n² are considered independently distributed. However, the constraint on the rate imposed by the RC-CMAB formulation makes it infeasible for the dociisionmmker to sample, through the pool of agents, the actions directly from the true distribu- tion T, s). The agents have to use proxy (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.
3.2 OPTIMAL SOLUTION FOR THE RC-CMAB
We model the environment as Discrete Memoryless Source (DMS), that generates states from finite alphabet S with probability Ps. emitting sequences of N symbols s = (8)))..,5N)) one per agent. We then denote with Q.x(m) the empirical probability of state in N.V. We also consider the sequence of actions aN and denote with Q.v (m,j) the empirical joint probability of the pair j) in N = ((s), a1) ai)..., (.), The whole picture can be seen in Fig. | In the figure above, the actions taken by the agents are denoted by to indicate that they can differ from a. However, we are interested in the probability distributions generating the sequences, thus we will denote with the random variables indicating both the actions at the controller and decision-makke side. We assume that the distribution Ps is known (or accurately estimated).
The decision-maker can observe the realization N of the contexts, and its task is transmit an index u E {1..... , B), and the agents can generate from u sequence N, such that Q.yan N is close to (SA((a) (s(s) ( (als), where closeness depends distortion measure E Ejd(qsa AN PsA)], which in general is not an average of a per-letter distortion measure. The problem is compression task in which the server has complete (or partial) knowledge of the states s. and wants to transmit a conditional probability distribution AAS to the agents, consuming the minimum amount of bits,
in such way that the empirical distributions Q,,,, given by the sequence induced by the agents
4

---

Under review as a conference paper at ICLR 2022
close to the joint distribution PSA induced by the policy. For distortion function d(QsA, PSA) that is 1) nonnegative, 2) upper bounded by a constant Dmaz- 3) continuous in QS and 4) convex in QSA. in Kramer & Savari (2007), the authors provide the rate-distortion function R R(D), i.., the minimum rate R log, B bits per symbol such that [ AN
AN. PsA)l I D, in the limit when N
N is arbitrarily large. The solution is given by
min R(D) Qa asd( I(S:
where QSAA = AIs is the joint probability induced by the environment distribution Ps and policy QAS: 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 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.
3.3 THE KL-DIVERGENCE AS DISTORTION FUNCTION
When applying TS to the RC-CMAB problem with limited communication rate, the decision- makker may not be able to induce the controller take samples from the true policy ", In Phan et al. (201)), the authors provide some theoretical guidelines to construct approximate sampling policies to make the posteriors, i.e., Pi concentrate achieving sub-linear regret. particular, they studied the case in which the sampling distribution Q differs from the target posterior æ, using (T, Q) as distortion measure, which denotes the a-divergence between the two, and is defined as
1 - ( (T))(((()))))) "+())==(++))) "d
Da Q)
ax(1 a
In Phan al. (2019). it is shown in Theorem 1 that, for 0, the condition (TT,,, Q) < 8 with 5 > O. cannot guarantee that the posterior converges in sub-linear time, even for very small values of 8. On the contrary, for a S 0, the authors provide a scheme that can guarantee sub-linear regret. In particular, they suggest to introduce an exploration term E o(1) such that Et=1 Pt co, and the actions are sampled from Qe with probability 1 1-pt. and uniformly random with probability Pt. while (T,, Q.) < 8 for all f. In this case, it is possible to obtain a sub-linear regret. Consequently, order to solve the proposed RC-CMAB problem, we decide to investigate this strategy with a = 0,
which leads to the reverse KL-divergence from Q to π, equivalently, the KL-divergence from
to Q, defined as (KI(Q, x) Exex Q(x) log ((x)
Q(w)) when x takes values in the discrete set X.
Consequently, to find the optimal constrained policy (a is), we need to find a solution to Eq. (2) which is 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 double minimization problem (Sec. 10.8,
(Cover & Thomas 2006a
Σ P(s)Q(a)s) log, ((a
R(D) = min
min
(4)
@()) (Qis
Q(a)
Following (Lemma 10.8.1, (Cover Thomas 2006a)), the marginal (* = Σ. ((x)Q(y/xx) has the property
Q'(x)= arg min DEL DxL((Pl))(og)e)))P(ttttt
(5)
Q(9)
that is, it minimizes the KI.-divergence between the joint and the product P(x)Q(y), AQ A This means that Q(a) obtained by solving Eq. (4) indeed the marginal over the actions induced by Q(als). 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 A and As are made of probability distributions, and the target measure is the KL-divergence, the algorithm does converge to the minimum [Csiszár Tusnády 1984). The process initialized by setting a random Qa(a), which is used as a fixed point to compute
Σ P(s) ((ass) logg ((ass)
Q (als) = argmin
(6)
Qo(a)
5

---

Under review as a conference paper at ICLR 2022
From (i(ass) we compute the optimal (a) by solving Eq. (5
which is simply the marginal
@i(a)= - P()))=2 The process iterated until convergence.
We now solve the inner minimization problem, i.e., Eq. 6 with fixed ((a). As we can see, the constraint on the distortion tries to keep QAIS close to x AAss. which is the target distribution. By minimizing the mutual information, we want aas close to QA as possible, which is the marginal known by the agent 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 conditional distribution QAIS 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 O, we need QAIS = T s. thus the rate is equal to Ep Dxr (Ta))|[TTa]] If and A are independent, i.e., the policy does not depend on the state, we have т A/S = πА thus the decision-maker does not need to send any bits to the agents, which can just sample A ~ тA- Moreover, if we find a distribution QA such that Epg [Dx r. ([I][=A|s)] & D, then the hest strategy is not to convey any message to the controller, as the constraint is already satisfied with rate RD = O. The problem is to find, among all conditional distributions ((ass) that satisfy the constraint, the one with the minimum divergence from Q(a), in order to minimize the rate -N B i.e. the number bits 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)' P(als)=-> Qal(als) Enres Q(a')²" P(a"|s)2->>
V
where 7" is s.t. Eps
D. The derivation provided in Appendix A.1
3.4 ASYMPTOTIC REGRET
To prove the results on the achievable regret, we need additional assumptions, which are contained in the Assumption 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 uni- formly bounded, i.e., bounded away from zero V(s, a). The proofs of both Lemmas are reported in the Appendix D
In the following, provide the minimum rate needed to achieve sub-linear regret in all states S. We now define H (AA) as the marginal entropy of the optimal arm, computed based on the marginal TT E. "s(sS (als), and defined H (A*) Σ. nt (a) log (()a and we prove that it is the minimum rate required to achieve sub-linear regret.
Lemma 3.1. If R H HA*)), then it is not possible to convey policy Qi(s, a) that achieves sub- linear regret in all states E S.
The following Lemma provides the achievibility part.
Lemma 3.2. R HAA"), then achieving sub-linear regret is possible in all states E S.
The consequence of this second Lemma is that, even if the exact TS policy n. cannot be transmitted Vt, as long as sufficient rate is available, i.c., 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 + co, and for all sub-linear regrets the regret-communication pair (p. 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
3.5 PRACTICAL CODING SCHEME
The above analysis allows us to characterize an information theoretical bound on the optimal per- formance, but does not provide constructive communication scheme. To find a practical coding scheme, we propose a solution that based on state reduction and computes a compact state repre- sentation. In essence, the decision-male constructs message containing the new state representa- tions (s)) E S of one for each agent, and send it over the channel. Once the agents have received

---

Under review as a conference paper at ICLR 2022
the message, they sample the actions according common policy Qa(alš), 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 2 different states to each agent. The idea is to group the states into where Qa(a[5) is the
2 M clusters $1,..., SM, minimizing E, ((())))ki((((())))((l)(
policy defined on the state 8(*) S.
To find the clusters and relative policies employ the well-known Lloyd algorithm, which is an iterative process to group states into 2 clusters. First of all, knowing the policy x. the decision- maker maps each state 8; K-dimensional point a' r--[st) Ak. finding [S] = different points a . Then, it generates 2 M random points μ ..... 1 E Ax as initial centroids, i.e,, representative policies, and iterates over the following two steps:
1. Assign to each point a² the class j E f1...., M such jhat arg min, Dx (x²lla))a")
i.c., minimizing the divergence between the representative μ²² and the original policy, which is the point a'. For each cluster j. we now define with S the set containing the states associated to the policies in the cluster.
2. Update , MM such that μ¹ = arg MEAx ExES, is still convex optimization problem, and can be solved again applying the Lagrangian multipliers. The solution is
which
Plo A(S))
1 IoE,, ((-ls)
Z
where the product has to be considered element-wise, A (S,) is the sum of the probabilities of states in Sy. i.e., A (S,) Eees, P(s), and Z is the normalizing factor. After com- puting the new centroids, we go back to step (1). The derivation of Eq. is provided in Appendix A.2
The process continues until the new solution does not decrease the KL-divergence between the M clustered and the target policy DæL (Qs(Q a(), Σ Eves,
Observation Note that the controller is assumed to know the N 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 N logz K >> BLA logz K, where À is the number of bits used to represent the values of the Probability Mass Function (PMF) Q= 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 zls the policy defined over the compressed state representation, with plast the last policy used to compute dle and with æ the updated target policy, we compute and transmit N rd every time D DKL(T (alst([TT) > BB
4 NUMERICAL RESULTS
In this section, we provide numerical results in support of our theoretical analysis. Additional ex- periments and details can be found in Appendix C
4.1 BATE-DISTORTION FUNCTION
In this first experiment, we analyze the rate-distortion function, and the related optimal (a)ss), when the distortion is given by the KL-divergence three different problems, when the numbers states, L, and of actions, K, are both equal to 16. The target policies π (als)) 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 = 2|s = j) 0.99 if [j/4] = 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
7

---

Under review as a conference paper at ICLR 2022
Shight
Rete- Dotertion Fund
sardcn UNOHMIIII
(b)
13
14
sdaped Nil
05
(c)
Figure 2: Rate-Distortion function for the 3 different experiments (a). T(als 8) and Q(als 8) in the third experiment, when the rate R is equal to (b). iTaas 8) and Q(a s 8) the second experiment, when the rate R is equal to 1.
the Shamnon entropy of Ps. as expected. Indeed, in this case, the action distributions are strongly correlated with the state, thus 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 at R(0) 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)) ~ (()n where Unifja is the uniform distribution over a set of 4 elements. In Fig. 2c the approximate distributions for state 8 are reported for the Deterministic and Random Deterministic cases, when R = 1.
4.2 CONTEXTUAL MULTI-ARMED BANDIT
We now analyze the RC-CMAB problem presented in Sec. and apply the clustered policy schemes to solve it. In particular, we compare the performance of the Perfect agent, which applies TS with- 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 = [ 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 lower bound on the performance. State distribution Ps is uniform over L = 16 states, and there are The threshold for changing the clustered policy is set to 3 = 0.2, and the communication rate con- straint to = 2.5. In this experiment, for each state 8; E S, the best reward is given by the arm aj such that i = j. with i.j E {0... 15). In particular, the reward behind arm when in state j is a Bernoulli random variable with parameter H4 = 0.8 i = j. whereas Jyy ~ Unif(p.0.75) if i * 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. aa). 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.
16 actions, N 100 agents, and the total number of rounds is T 200.
In Fig 3 (b), the KL-divergence between the last policy used to compute the compressed state rep- resentation, i.e., mlast 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 8 = 2 is highlighted. indicating when a new cluster policy has to be sent. In this experiment, the decision-make had to send a new policy, average, once every rounds. Fig. 4 (a) reports the regret at state s 10 (the other
8

---

Under review as a conference paper at ICLR 2022
plots can be in Appendix C.2 for the four different agents, defined in Eq. We that both the Cluster and the Comm agents can achieve sub-linear regret this particular state. In Fig. (b), the average rewards obtained by the agents are reported, for the different states separately. We can see that the developed scheme still able to achieve good performance.
Agents Communication
25
1.0
refect
05
Comm
10
Duster
23
30
75
180
325
150
373
202
25
350
135
150
175
200
(a)
(b)
Figure 3: Asymptotic rates to convey the Perfect and Comm policies, and the bits used by the Cluster agent, averaged over runs (a). DKL ( [[TT) averaged over 5 runs (b).
Regret for State 10
Perfact
Quarae
200
Cluster
200
110
150
Earation
(a)
(b)
Figure 4: Cumulative regret for different agents, together with the performance of the Marginal agent, evaluated for the state 10 (a). Average reward per state (b).
CONCLUSION
We have studied the RC-CMAB problem, in which an intelligent entity, i.e., the decision-make observes contexts of 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 connected to the decision-maker through a rate-constrained communication link. First, cast the problem into the proper information-theorude framework, formulating it as a policy compression problem, and provided the optimal compression scheme the limit of an infinite number of agents, when the adopted distortion measure the KL-divergence between the compressed policy adopted by the controller and the policy of the decision-maker. We then char- acterize the minimum needed rate 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 perfor- mances 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 is possible to save communication resources when training multi-agent system like the one considered. We believe that this work can serve first step towards understanding the fundamen- tal performance limits of multi-agent decision- pecision-mmaiin 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 reinforcement learning problems.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Mridul Agarwal, Vaneet Aggarwal, and Kamyar Arizzadenesheli. Multi-agent multi-armed bandits with limited communication. In arXiv:2102.08462 [es], 2021.
Rudolf Ahlswede and Imre Csiszár. Hypothesis testing with communication constraints. 32(4): 533-542, Jul. 1986.
Toby Berger. Decentralized estimation and decision theory. In IEEE 7th. Spring Workshop on Inf. Theory, Mt. Kisco, NY, Sep. 1979.
Djallel Bouneffouf and Irina Rish. survey on practical applications of multi-armed and contextual bandits. arXiv Ls.LG: 10040, 2019.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecom- munications and Signal Processing). Wiley-Interscieence, USA, 2006a. ISBN 0471241954.
Thomas M. Cover and Joy A. Thomas, Elements of Information Theory (Wiley Series Telecom- munications and Signal Processing). Wiley-Intersccience, USA, 2006b.
Imre Csiszár and Gabor Tusnády. Information Geometry and Alteraatng Minimization Procedures. Statistics and Decisions, Supplement Issue, pp. 205-237, 1984.
Jakob N. Foerster, Yannis M. Assael, Nando de Freitas, and Shimon Whiteson. Learning to Com- municate with Deep Multi-Agent Reinforcement Learning. 1605 [cs], May 2016. arXiv: 1605.06676.
Osama A. Hanna, Lin F. Yang, and Christina Fragouli. Solving multi-arm bandit using few bits of communication. In 38 th International Conference on Machine Learning. 2021.
Serhii Havrylov and Ivan Titov. Emergence of language with multi-agent games: Learning com- municate with sequences of symbols. pp. 11, 2017.
Maximilian Igl, Kamil Ciosek, Yingzhen Li, Sebastian Tschiatschek, Cheng Zhang, Sam Devlin, and Katja Hofmann. Generalization reinforcement learning with selective noise injection and information bottleneck. In Advances in Neural Information Processing Systems, volume 32, pp. 13956-13968, 2019.
Mikolaj Jankowski, Deniz Gündüz, and Krystian Mikolajezyk. Wireless image retrieval at the edge. IEEE Journal Selected Areas in Communications, 39(1)889-10) 2021. doi: 10. 10.1109/JSAC. 2020.3036955.
Cem Kalkanli and Ayfer Ozgur.
Asymptotic
convergence
Thompson sampling. In
trXiv:2011.039/770 2020.
Gerhard Kramer and Serap A. Savari. Communicating probability distributions. IEEE Transactions on Informatio Theory, 53(2):118-525, 2007. doi: 10. 10.1109911.222006889000
Angeliki Lazaridou, Alexander Peysakhovich, and Marco Baroni. Multi-agent cooperation and the emergence of (natural) language. arXiv:1612.07180 [cs], March 2017. arXiv: 1612.07182.
Hongju Park and Mohamad Kazem Shirani Faradonbeh. Analysis of Thompson sampling for par- tially observable contextual multi multi-armed bandits, 2021.
Jihong Park, Sumudu Samarakoon, Mehdi Bennis, and Mérouane Debbah. Wireless network intel- ligence at the edge. Proceedings of the IEEE, 107 2222292-222, 2019.
My Phan, Yasin Abbasi Yadkori, and Justin Domke. Thompson sampling and approximate infer- ence. In Advances in Neural Information Processing Systems, 2019.
Daniel Russo. Simple bayesian algorithms for best arm identification. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (eds.), 29th Anmual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. 1417-1418, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL https: http///pecc.c..ccce//eeopoo mlr., .....ress.//////e v49/ russcl 6. html
httpps://pzooeeiinggg
10

---

Under review as a conference paper at ICLR 2022
Sainbayar Sukhbaatar, Arthur Szlam, and Rob Fergus. Learning multiagent communication with backpropagation. In Proc. of 30th Int'l I Conf. on Neural Information Proc. Systems, NIPS' 16, pp- 2252 2260, Red Hook, NY, December 2016.
William R. Thompson. On the theory of apportionment. American Journal of Mathematics, 57(2):
450-456, 1935.
Róbert Torfason, Fabian Mentzer, Eirikur Ágústsson, Michael Tschannen, Radu Timofte, and Luc Van Gool. Towards image understanding from deep compression without decoding. In International Conference Learning Representations, 2018.
Aolin Xu and Maxim Raginsky. Information- lower bounds on Bayes risk in decentralized estimation. IEEE Transactions on Information Theory, 63(3):1580-1600, 2017. doi: 109/ TIT.2016.2646342.
Yuchen Zhang, John Duchi, Michael Jordan, and Martin J Wainwright. information-theorett lower bounds for distributed statistical estimation with communication constraints. In Advances in Neural Information Processing Systems, volume 26, 2013.
APPENDIX
A POLICIES DERIVATION
A.1 OPTIMAL POLICY
To solve this problem, we solve the related Lagrangian
[(Q(a)s), EP(s) Σ log
Q(als)
+
P(s))
Σ P(s) Σ ((als) log Q(als) P(a|s) D
Qa
+ Σ P(s) (((ls))))))
Q(als) -
where the Lagrangian multiplier À has to be optimized to meet the constraints on the divergence, whereas μ ensures that the solution is probability distributions, i.c., the elements
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 ((ass) and set it to zero
a P(s) log Q(als) oQ(als)
P(s)
+ P(s) Q(al(a)s))
((a)
2(a)
Q(als)
+ AP(s) log P(als) +1) +p((s) (+)ss) =
finding
Q(als)
log (a) -
((als) 1+1 = - -m-(n+) ((a))()))(((ss)
Q(als) =6 - Q(a) + P(als)
and now we rewrite with 7 T 7 [0, 1}, and such that -(+t)) The solution has thus the shape
is the normalizing factor.
(())s
(a(ass) Ev'es ((a))=
VsES,
By the convexity of KL-Divergence and its triangular inequality, know the solution lies the boundary of the constraints, i.c., when Epg [Dxr. (k, D. Consequently, we can numeri-
cally find 7" s.t. Ep, [Dxr(Q,) P)] D. we solve Eq. 6
11

---

Under review as a conference paper at ICLR 2022
A.2 UPDATE CENTROIDS
Again, we compute the optimal centroids by solving the Lagrangian
A(H(,A)= E
P(s)
Σ
ne log
pd (a|s) +
Σ
1ma-11
SES;
aEA
NacA
taking its derivative and solving the equality
@C(Ha,
Σ
P(t)
log T(als) +1 +
sES,
finding
log ( = Σ
P(s) + AA(S)) +
sES,
P(s) log (als) +1+ A(S))
log 14
Σ
sES, (S,)
P(e)
n² II MSES, <-1ss) A(33)
where the normalizing factor, obtaining the shape expressed in Eq. 8
12

---

Under review as a conference paper at ICLR 2022
B PRESENTED ALGORITHMS
In this appendix, the algorithms for the theoretically-optimal and cluster policies are described.
B. THEORETICAL OPTIMAL POLICY
This is the pseudocode of the algorithm the decision- side, when adopting the information- theoretic 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 {l...., A), and with U the uniform probability over the set B.
Algorithm Optimal Policy
Input rate Rt n" agents N, n" actions K and state distribution Ps Initialize Thompson Sampling policy я, and compressed policy Q(-Is) to Unif[k]
foreach t I..... T do
Observe st (st, St
Sample at (.r,,, 0r,N) from Q(1ss)
Code a² into u1 = fe(a;)) and transmit the controller
Observe ry = (rt,1,.... Tt.N)
Update action posteriors TT-(s) using the Thompson Sampling Algorithm
Update (als) using the Blahut-Arimoto Algorithm (Iterate over Eq. and Eq.
B.2 CLUSTER POLICY
This is the pseudocode of the algorithm the decision-maker side, when adopting the cluster policy. The task for the controller is to sample, at time and for each agent i, the action a, according to the last received centroid ()(s.)) whose components convey the action probabilities.
Algorithm 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 μı for j ,,...,2 2 using with Lloyd algorithm and the rule in Eq. Transmit the centroids μı to agents. last π
foreach t L..... T do
Observe 5/" (st.1.... St,N) if DKL (nalas( (T) 3 then
Update the centroids μı using with Lloyd algorithm and the rule in Eq. Transmit the centroids μy to all agents.
Vst,i compute the index (st,s) indicating its belonging cluster Transmit the vector j :
Observe r:N (rt,1,..., Tt,N)
Update action posteriors π (-18) using the Thompson Sampling Algorithm
13

---

200 Under review as a conference paper at ICLR 2022
C EXPERIMENTS
In this section, additional experiments are provided to clarify the proposed scheme, and quantify the trade-off's between rate and regret.
C. STATE REPRESENTATION
In Fig. we report the policy clustering results when applying the coding scheme explained in Sec. 3.5 when Rt bits can be used to represent 20 randomly generated policies. In the figure, it is possible to 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.
Figure Clusters and their representatives with L 20 and
C.2 DETERMINISTIC
In this section we reported some more details on the RC-CMAB experiments presented in Sec. 4.2
Comm
Cluster
Pefect
Comm
AF
3.4
052
3.2
(a)
(b)
Policy KL-dlvergence
Comm Cluster
Kt-diverge senggeeee
1.5
1.0
0.5
0
25
30
75
100 Iteration
125
150
175
(c)
Figure 6: Best action probability for a given state, for the posterior =<alss) (a) and compressed policy Qsa*(s) (b) for the different agents. KL.-divergence between the agents' action posteriors, and the target one (c).
14

---

Under review as a conference paper at ICLR 2022
Regret for State
Regret for State
Perfect
Perfect
500
Comm
Marginal
400
Marginal
Cluster
Cluster
Regret
300
200
100
0
75
175
200
25
125
150
Iteration
Iteration
Regret
Regret
Perfect
350
Perfect
Marginal
300
Marginal
Cluster
250
Cluster
300
Begret
200
200
150
50
75
100
125
150
175
200
25
50
73
100
125
150
175
200
Iteration
Iteration
Regret for State
Regret for State 5
Comm
500
Comm
400
Marginal
Regret
100
200
200
75
100
150
375
200
25
50
125
130
200
Iteration
Iteretion
Regret for State
Regret for State 7
500
Reffect
Perfect
Marginal Clister
Marginal
Cluster
.00
Ragret
200
200
100
100
0
175
15

---

Under review as a conference paper at ICLR 2022
Regret for
Regret
Perfect
Perfect
800
500
300
Cluster
Marginal
400
Cluster
Marginal
Regret
400
Ragnet
knn
200
100
50
75
100
125
150
175
200
25
50
75
100
125
15C
175
200
Iteration
Iteration
Regret State
Regret for State 11
500
Comm
Comm Cluster
Marginal
400
Cluster
Regret
300
300
100
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Iteration
Iteration
Regret for State 12
Regret for State 13
500
Perfect
300
Perfect
Comm
Comm
400
Marginal
400
Marginal
900
Regret
300
200
200
100
100
Iteration
Regret State
Regret for State 15
600
Perfect
Perfect
400
500
Marginal
Marginal
300
Cluster
400
Cluster
Rogret
300
200
100
100
75
100 Iterationn
175
25
125
150
Iteration
Figure 8: Cumulative average regret one std for the different agents, from state 0 state = 15
16

---

Under review as a conference paper at ICLR 2022
C.3 B-BLOCK EXPERIMENT
In this second RC-CMAB experiment, the setting is similar to the one presented above, but the best action response is not one-to-one mapping with the state. Again, a {0, ..... 15) and {O...., 15), but the Bernoulli parameter (s) for action in state 8 is 0.8 if | = a, and sampled
uniformly in (0, 0.75] otherwise. Thus, the best action responses are grouped into different classes,
depended on the state realization. In this case, the rate is limited to R = 2.
Agents Communication Rate
ginal
Perfect
2.5
Comm
Cluster
2.0
2.4
0.0
(b)
Figure 9: Block experiment: asymptotic rates to convey the Perfect and Comm policies, and the bits used by the Cluster agent, averaged over runs (a). Average reward achieved in each state by the pool of agents (b)
1.2
1.0
0.7
3.0
State
(b)
Policy KL-divergence
Cluster
Eddivergennce
0.5
0.0
Iteration
(c)
Figure 10: Block experiment: Best action probability for given state, for the posterior π (a") [s) (a)
and compressed policy Q(a*ls) (b) for the different agents. KL-divergence between the agents' action posteriors, and the target one (c).
17

---

Under review as a conference paper at ICLR 2022
Regret for State
Regret for State
900
Perfect
Perfect
Comm
Marginal
Marginal
Cluster
Cluster
300
Regret
200
200
100
75
100
175
25
125
150
Iteration
Iteration
Regret
Regret
500
Perfect
500
Perfect
400
Marginal Cluster
400
Marginal
Cluster
Begret
300
50
75
100
125
150
175
200
25
50
73
100
125
15C
175
200
Iteration
Iteration
Regret for State
Regret for State 5
500
Comm
Comm
Marginal
400
Regres
Regret
200
200
100
100
75
100
150
375
200
25
50
125
130
200
Iteration
Iteretion
Regret for State
Regret for State 7
400
Reffect
Perfect
400
350
Marginal
Marginal
300
Clister
250
Cluster
Begret
200
200
150
100
100
0
175
18

---

Under review as a conference paper at ICLR 2022
Regret for
Regret
600
Perfect
Perfect
300
500
Marginal
Marginal
Cluster
Cluster
Ragret
200
300
130
100
100
0
50
75
100
125
150
175
200
25
50
75
100
125
15c
175
200
Iteration
Iteration
Regret State
Regret for State 11
600
Comm
Comm
Marginel
Marginal
Cluster
Cluster
Reglet
Begret
300
200
100
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Iteration
Iteration
Regret for State 12
Regret for State 13
Perfect
Perfect
Comm
Comm
900
Marginal
400
Marginal
250
Regret
300
100
100
Iteration
Regret for State
Regret for State 15
Perfect
Perfect
Marginal Cluster
Marginal
400
Cluster
Rogret
300
200
100
100
0
75
100
175
25
125
150
Iterationn
Iteration
Figure 12: Block experiment cumulative average regret one std for the different agents, from
state s = 0 to state = 15
19

---

Under review as a conference paper at ICLR 2022
C.4 REGRET VS NUMBER 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 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 is equal to 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 bits can achieve performance comparable with the and 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 a cluster contains, for example, one state, it will convey best policy, achieving sub-linear regret. On the contrary, when cluster contains more states, the representative policy can fail to achieve optimal performance, those are substantially different.
Regret for State
Regret for State
350
400
B =
300
300
200
150
100
50
100
1.00
150
200
250
300
350
Iteration
Iteretion
Regret for
250
300
250
Regrot
200
200
150
100
50
1000
150
200
750
300
350
50
100
150
700
250
300
853
Iteration
Iteration
Regret for State
Regret for State 5
300
300
250
300
200
200
150
100
50
0
Regret for State
Regret State 7
400
B
900
250
200
Regrat
200
1.5
100
100
300
Iteration
Iteretion
20

---

Under review as a conference paper at ICLR 2022
Regret
250
300
250
250
Regrot
200
130
100
30
100
150
230
250
300
350
50
100
130
200
250
300
350
Iteration
Iteration
Regret for State 10
Regret for State 11
300
200
Regret
200
100
100
0
Regret for State
Regret for State 13
400
200
Rogret
150
100
100
250
300
350
Iteration
Iteration
Regret
Regret
400
400
300
250
3pgtet
200
150
100
50
100
150
230
250
300
350
30
100
150
200
250
300
250
Iteration
Iteration
Figure 14: Deterministic experiment: cumulative average regret = one std for cluster policy, when {1,2,3, 3, 4), from state to state
21

---

Under review as a conference paper at ICLR 2022
D REGRET BOUND
To prove our statements, we define with (X) and (x; ((:Y) Y) the marginal entropy and mutual information w.r.t. to the joint probability q, i.e.e ((A)) Hx (A). We start by proving Lemma D.1 Lemma D.I. If the exact Thompson Sampling policies ne (a) achieve sub-linear Bayesian regret for all state 8 E S, then lim,- > 1x (S; A) lim FT, (A) (AA).
Proof. First of all, write I,, (S) H., (A) H (AIS). Following Theorem 2 from Kalkanli & Ozgur 2220)), if T. (a(a)) achieves sub-linear regret Vs E S, then vss e S
lim (a a when a" is the optimal arm
lim (a a
when a' #a
Consequently, we have that in the limit me (a|s) is deterministic function, thus
lim H., (A* 0,
+000
which concludes our proof.
Then, we prove Lemma 3.1 which is repeated below.
Lemma 3.1 If R < HA*), then it is not possible to convey policy Qe(s, a) that achieves sub- linear regret in all state S.
Proof. Following Lemma 10 in Phan al. (2019). lim Te (a and Dxz (Qul( < Vt, for some e >> 0, then lim Q. 1. inducing lim,- -o D DK.. [Q+|| = 0.
Now, for any policy Qt, if the minimal rate to convey it, RG le, (S; A), is below the threshold of the optimal policy, i.e., R₁ HA*).. by Eq. (2. we have
DEL (Qill=))
(10)
which holds also in the limit. Otherwise, we would have policy Q, s.t. DEL (Qill=*) 0. which could be conveyed at a rate strictly below that characterized by Eq. (2). which would contradict with the definition of the rate- dieedistootion function.
Consequently, by Lemma 10 in Phan et al. 2019) and Eq. (O), there cannot be any e > s.t. lim;-xoc DEL (Q+ll=e) e; and hence, lim; oo DRL. (Qrll co.
However, if lim DKL (T. = oc, 3(s a) E S x s.t. limy- (c(als) = c > 0, when # a". This implies that, at step (s plays sub-optimal arm in state 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 E S.
Proof. We define by RT the rate needed to convey the TS policy perfectly to the controller at time t, and let 8 > 0 s.t. R = ((A") + 8, where R is the available communication rate. We now provide a scheme that guarantees sub-linear regret.
First, generate P: parameters as in Sec. 3.3 As long R R, with probability Pe play a uniformly at random, and with probability I-Pt. play according to a policy (a(a)s), which satisfies the cate-distortion constraint (A: < R under (a(as), which be transmitted to the controller, and will have a bounded reverse KI. divergence from the TS policy म. at time f. Following Lemma 14 in Russo (2016). in this way enough exploration is guaranteed for the TS policy to concentrate, and there exists finite to s.t. Vt > to. R < H (A*) + 5. This means that, for the first to rounds, both the target and the approximating policies are playing sub-optimal arms with non-zero probabilities. However, their average gap is within constant, given the average rewards are bounded within [0, 1). Then, Vt > to it is possible to play the exact TS policy, leading to the optimal policy for all future steps, and hence, a sub-linear regret.
22


Reviews:
[{"review_id": "Yme1Mri_uB6", "reviewer": "Reviewer_vEGv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is sound and of certain interest. One knock of this paper is that the results were largely adapted from known information-theoretic results: the optimal bound was derived based on Kramer&Savari; TS for RC-CMAB was based on the double minimization problem in Cover&Thomas as well as the well-known Blahut-Arimoto algorithm; the practical coding scheme was based on the well-known Lloyd algorithm for clustering. Putting these pieces together is not trivial, I must admit. However, the overall novelty is thus limited. \n\nAnother question is about the problem setting. The assumption that each agent's state $s_{t,i}$ is observed by the decision-maker, but not the agent itself, is very strange. Since the state is agent-dependent, agent $i$ generally already has access to the state $s_{t,i}$, which then makes this problem a decentralized MP-MAB problem (with contextual MAB). The authors should clarify why they make the assumption that only the central decision-maker can observe all agents' states, but not the agents themselves. In fact, the practical coding scheme is about sending the state (via a compact state representation) to the corresponding agent. This may not be necessary to begin with in practice. Also, with the aforementioned argument, the controller \"decoder\" function $g_t^{(N)}$ should have the joint states of all agents as an input. This would enhance the decoder design.  ", "summary_of_the_paper": "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.", "summary_of_the_review": "A solid work overall, but with some questions on the novelty and assumptions. Will be open to author responses and adjust the score accordingly. \n\n======\n\nPost-rebuttal update: I thank the authors for addressing my concerns on the availability of state information to the decision-maker versus the agent. I hope that the authors add these details, especially the factory example, to the paper. My other reviews remain the same.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VkPOXOXSnsu", "reviewer": "Reviewer_CLeX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Major comments:\n1. Most importantly, there is no complete theoretical analysis (e.g. the upper bound/lower bound on the regret of the algorithm.)\n1. The algorithm should be explicitly written out with its pseudocode. \n1. By the end of Section 1, it states that the communication is one-way from the decision-maker towards to controller. However, as the decision-maker can observe the realization history, it is a bit strange not to consider that as communication. Besides, how the goal of this work is different from existing papers is confusing.\n2. The problem setup is not clear: is the state i.i.d. sampled from the distribution $P_S$ or not?\n3. The relation between the constraint quantities $(\\rho,R)$ and the discussions in Section 3 is not clear.\n4. The constraints seem to be placed in the posterior probabilities involved in the TS algorithms. What if we consider UCB-class algorithms?\n5. The definitions of $D_\\alpha$ and reverse KL divergence $D_{KL}$ is missing. Usually, we denote the original KL divergence by $D_{KL}$.\n6. In Section 3.3, it states ''If $S$ and $A$ are independent...'', I don't think it's a common assumption in contextual bandits.\n\nMinor comment:\n1. The citation style is not so good: for instance, it should be \"In Phan et al. (2019) ...\" instead of \"In (Phan et al., 2019)...\"\n ", "summary_of_the_paper": "This paper focus on the contextual multi-armed bandit with communication constraints. It provides some discussions and numerical results.", "summary_of_the_review": "Overall, this works lacks complete analysis, which is not usual in a bandit paper, and the relation between the background and the discussions is not clear. Hence, the contribution of the work is not clear. The detailed comments are as above.\n\n\n\n================================\nI appreciate the efforts of authors to add on theoretical results during the rebuttal period, and decide to raise the ranking from 3 to 5.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9DZ6suJsQB5", "reviewer": "Reviewer_Cm2b", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a well-written paper, and in particular I think the paper does a good job in the following aspects: 1. The RC-CMAB problem of interest is well-motivated in the introduction (e.g. with the personalized ad placement example); 2. The explanations for modelling the problem as a policy compression problem are clearly conveyed, and the relevant technical discussions on the distortion function as well as the clustering coding scheme (over states) are concise and easy to follow; 3. The analyses in the numerical result section are comprehensive and thorough, and I find the numerical illustrations related to the asymptotic rates to convey the considered policies (Fig. 4) quite insightful and interesting. Furthermore, I particularly liked the fact that the ideas behind the clustering coding scheme are simple and intuitive (since the idea of compressing states in clusters and transmitting a policy for each cluster is straightforward and natural), which is a huge plus from both a theory and practical perspective. \n\nIn terms of weaknesses, my main concern is that the paper lacks theoretical performance guarantees for the clustering coding scheme. I believe including a characterization of how regret depends on the number of states, the rate constraint, number of actions, etc. would provide us with a more in depth understanding of the performances of the clustering scheme in various scenarios. On a related note, I am specifically interested in how the proposed clustering schemes’ performance decays as the total number of states grows, because intuitively, more states would induce larger clusters and hence larger distortion in the policy defined over the compressed states (compared to the target policy). I am bringing this up because the paper uses personalized ad placements as a motivating example, and in such markets, typically the content owner’s valuation for a user view (i.e. impression) or conversion serves as the ``context’’ (or state), and may take a wide range of values. If providing theoretical analyses for the dependence on the state space is infeasible, at least having some experiments that address related issues would be beneficial.\n", "summary_of_the_paper": "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. \n", "summary_of_the_review": "The paper is well-written and well motivated. The technical discussions are concise and clear. The analyses for numerical results are comprehensive and thorough.\n\nWeaknesses: the paper would be much stronger if it includes theoretical guarantees for the clustering scheme, and also results/discussions/experiments on how the cluster scheme’s performance decays with the number of states.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7zC-nPGdVAD", "reviewer": "Reviewer_mXFx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n* The paper proposes an original problem that combines the challenges of bandit modelling and information constrained communication problems. I particularly like that this problem has achievability constraints and elegantly makes use of information theory to solve a contextual bandit problem. \n* The problem is motivated by a real real-world task\n\nWeaknesses:\n* There are some inconsistencies and imprecisions in the writing that make it hard to follow. Section 2 defines a lot of quantities and regrets and gains, etc. that are not really analyzed afterwards, or I missed it: what do you mean to say about G and \\rho and R ? Also, how is R defined exactly (the “communication rate”), is it some ratio of N and B or something ? \n* The paper does not have regret bounds, I guess it was out of your scope, but can you comment on that ? You briefly talk about problems that are “achievable” but then we don’t really know what kind of regret we could expect it seems. \n* Algorithm needs to be clearly outlined: You give very detailed explanations on your algorithms but for the sake of readability we need a pseudo-code. At the moment, I am struggling mending the pieces between all the different optimization procedures to solve and what needs to be done when and by whom. Can you please outline a pseudo-code and upload it so I can check that my understanding corresponds to what you are doing ? \n* Minor: Lower-level literature review: I feel like the background is given in the related work but I am surprised you were not able to connect your work better with the existing literature on contextual bandit. Perhaps contextual bandits with context uncertainties, or Partially Observable MDPs ? \n\n\nMinor: \n* section 3.3 : “posterior \\pi convergences” -> “converges”", "summary_of_the_paper": "This paper studies a contextual bandit problem where the decision-maker must communicate its intended actions (given observations of the contexts) to a controller through a constrained communication channel. The original part of the paper is that the “bandit algorithm” must encode its actions into a compressed version that then serves to the controller. \n\n", "summary_of_the_review": "TL;DR: The paper is a bit hard to follow for the non-expert in compression that I am (arguably like many of the bandit community) so I am not sure of my evaluation and I hope to be able to clarify it during the rebuttal / discussion phase. I cannot make a strict recommendation for now but I will update my score after the rebuttal phase. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Summary: This paper studies a contextual bandit problem where the decision-maker must communicate its intended actions (given observations of the contexts) to a controller through a constrained communication channel. The original part of the paper is that the “bandit algorithm” must encode its actions into a compressed version that then serves to the controller. In that sense, the controller must cluster the problems for the decision maker to simplify communication.

Discussion: Most reviewers appreciated that the paper is well-written and proposes an original problem. The main commonly issue is that of a lack of regret analysis. The authors included an additional theoretical result giving a necessary condition for sublinear regret but the committee would still appreciate a more in-depth study of the performance of the proposed algorithm, given that the condition is satisfied. One possible direction is to connect this work with the literature on "Clustering of bandits" (CoB) as raised by reviewer mXFx. The authors claim that this paper is only mildly related but the committee would kindly insist that linear rewards are just a generalization of multi-armed bandits, that there is also a finite state space in CoB (finite population) and it seems possible to reduce the proposed problem to CoB under some assumptions. In that regards, it would be important that a more thorough review and comparison of that line of work is done in the main paper (note also "Latent Bandits" and related papers), even though we agree that the proposed approach is different and we appreciate its originality.

Overall, the paper is borderline, and the committee did not reach a consensus. 

Decision: Reject
Decision: Reject