Learning from Distributed Users in Contextual Linear Bandits Without Sharing the Context
Authors: Osama Hanna
Lin Yang
Christina Fragouli
Venue: NeurIPS 2022 Accept (2022)
Keywords: bandits
contextual bandits
linear bandits
distributed contextual bandits
bandits with communication constraints

Abstract: Contextual linear bandits is a rich and theoretically important model that has many practical applications. Recently, this setup gained a lot of interest in applications over wireless where communication constraints can be a performance bottleneck, especially when the contexts come from a large $d$-dimensional space. In this paper, we consider the distributed contextual linear bandit learning problem, where the agents who observe the contexts and take actions are geographically separated from the learner who performs the learning while not seeing the contexts. We assume that contexts are generated from a distribution and propose a method that uses $\approx 5d$ bits per context for the case of unknown context distribution and $0$ bits per context if the context distribution is known, while achieving nearly the same regret bound as if the contexts were directly observable. The former bound improves upon existing bounds by a $\log(T)$ factor, where $T$ is the length of the horizon, while the latter achieves information theoretical tightness.

Learning from Distributed Users in Contextual Linear Bandits Without Sharing the Context
Osama Hanna
Lin Yang
University of California, Los Angeles
University of California, Los Angeles linyangducla. edu
ohannalucla.
Christina Fragouli
University of California, Los Angeles christina. faristina.fragouli cacooullillll....m Sucla. edu
Abstract
Contextual linear bandits is a rich and theoretically important model that has many practical applications. Recently, this setup gained lot of interest in applications over wireless where communication constraints can be a performance bottleneck, especially when the contexts we consider a distributed memoryless contextual linear bandit learning problem, where the agents who observe the contexts and take actions geographically separated from the learner who performs the learning while not seeing the contexts. We assume that contexts are generated from a distribution and propose method that uses z= 5d bits per context for the case of unknown context distribution and 0 bits per context if the context distribution is known, while achieving nearly the same regret bound as if the contexts were directly observable. The former bound improves upon existing bounds by a log(T) factor, where T is the length of the horizon, while the latter achieves information theoretical tightness.
from large d-dimensional space. In this paper,
1 Introduction
Contextual linear bandits offer a sequential decision-making framework that combines fundamental theoretical importance with significant practical popularity 3 it offers tractable way to capture side information (context), as well as a potentially infinite set of decisions (actions). The most promi- nent application is in recommendation systems (3C) but has also been used in applications such as virtual support agents
33 clinical trials 12] transportation systems (9] wireless optimization
26 25
health
[0 robotics
31 and online education 34]
In this paper, we develop algorithms that support the deployment of contextual linear bandits in distributed settings. In particular, consider the where a central learner wishes solve contextual linear bandit problem with the help of transient agents. That is, we assume that the agents do not keep memory of past actions and may be present for the whole duration of learning; learning in our setup can happen thanks to the persistent presence of the central learner. We view the central learner as "knowledge repository". that accumulates knowledge from the experience of the transient agents and makes it available to next agents. The central learner, through the information keeps, could help passing by devices decide how perform action, for example: passing by drones decide how to perform a manoeuver; agricultural robots decide what amounts of substances such as pesticids release; and passing by mobile devices decide which local restaurants recommend.
The main challenge we try to address this paper is the efficient communication of the context the agents experience. More specifically, in setup, each time agent joins, she receives from the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

central learner information on the system, such as current estimates of the system parameters; she observes her current context, selects and plays an action and collects the corresponding reward. Note that although the distributed agent knows her context, the action she plays and the observed reward, the central learner does not - and needs this information to update its estimate of the system parameters. The context in particular can be communication heavy- in the examples we mentioned before, for drones the context could be their navigation capabilities, physical attributes, and enviromental factors such wind speed; for agricultural robots, it could be images that indicate state of plants and sensor measurements such as of soil consistency; for restaurant recommendations. it could be the personal dietary preferences and restrictions, budget, and emotional state. Moreover, because of geographical separation, the central learner may not have any other way to learn the context beyond communication. Unlike the reward, that is usually a single scalar value, the context can be a vector of a large dimension d from an infinite alphabet, and thus, communicating the context efficiently is heavily nontrivial.
The technical question we ask is, how many bits do we need to convey per context to solve the linear bandit problem without downgrading the performance as compared to the non-distributed setting?
In this paper, we design algorithms that support this goal. We note that our algorithms optimize the uplink communication (from the agents to the central learner), and assume unlimited (cost-free) downlink communication. This is a standard assumption in wireless 7 33 21 for several reasons: uplink wireless links tend to be much more bandwidth restricted, since several users may be sharing the same channel; uplink communication may also be nattery-powered and thus more expensive to sustain; in our particular case, the agents may have less incentive communicate (provide their feedhack) than the central learner (who needs to learn). Having said that, we note that our algorithms (in Sections
3 and 4 make frugal use of the downlink channels, only using them to transmit system parameters.
Below we summarize our main contributions:
1. We show the surprising result that, if the central learner knows the distribution of the contexts, we do not need to communicate the context all - the agent does not need to send any information on the actual context she observes and the action she plays. It is sufficient for the agent to just send 1 bit convey quantized information on her observed reward and nothing else. But for this very limited communication, the central learner can learn a policy that achieves the same order of regret as if full information about the context and reward is received. This result holds for nearly all context distributions and it is the best we can hope for zero bits of communication for the context.
2. If the central learner has no knowledge of the context distribution, we show that R 5d bits per context (where d is the context dimension) is sufficient to achieve the same order regret as knowing the context in full precision. Note that previous algorithms, that rely on constructing 1/TT-et for the set of feature vectors, use (d log 7) bits per context to achieve the same order regret, where T is the length of the horizon 24 and require time complexity of ((T')) which is exponential in d.
Related Work and Distinction. Contextual linear bandits is rich and important model that has attracted significant interest both in theory and applications R 24 Popular algorithms for this setup include LinUCB 11 57 and cotextual Thompson sampling
Under Assumption [ these algorithms achieve a regret of Ö(dVT), where d is the dimension of an unknown system parameter and T is the time horizon, while the best known lower bound for this setup is ((dvTT) (37]. These algorithms assume perfect knowledge of the contexts and rewards. Within this space, our work focuses on operation under communications constraints in a distributed setting.
There is large body of work focusing on distributed linear contextual bandits settings, but mainly within the framework of federated learning, where batched algorithms have been proposed for communication efficiency [43] 41 G. 5. 23 that aggregate together observations and parameter learning across a large number of iterations. This is possible because in federated learning, the agents themselves wish to learn the system parameters, remain active playing multiple actions throughout the learning process, and exchange information with the goal of speeding up their learning 4 T. In contrast, in our setup batched algorithms cannot reduce the communication cost because each agent only plays a single action; this may be because agents are transient, but also because they may not be interested in learning this may not be task that the agents wish to consistently perform- and thus do not wish devote resources to it. For example, an agent may wish to try a restaurant in a special occasion, but would not be interested in sampling multiple restaurants/learing recommendation system parameters. In other words, we consider a scenario where the user benefits from receiving an action (or policy) from the central learner, e.g., a recommendation. In response, the user gives

---

feedback to the central learner in termss of (compressed) context/reward. The compression operations benefit the user by helping reduce her communication cost. In principle. the user is not required to respond. But the central learner will be able to learn whenever there is feedback; creating an incentive for the user to respond could be an interesting future topic. Our setup supports a different (and complementary) set of applications than the federated learning framework, and requires new set of algorithms that operate without requiring agents to keep memory of past actions
There is long line of research on compression for machine learning and distributed optimization, e.g., compression for distributed gradient descent 40
and distributed inference [19]. However, such schemes are not optimized for active learning applications. Our compression schemes can be seen as quantization schemes for contexts and rewards tailored to active learning applications.
Our work also differs from traditional vector compression schemes 15 that aim to reconstruct the data potentially with some distortion (achieve rate-distortion trade-offs). In our case, we do not aim to reconstruct the data, but instead to distinguish the best arm for each context. Indeed, using 0 bits, as we do in Section g
we cannot reconstruct meaningful estimate of the context.
To the best of our knowledge, our framework has not been examined before for linear contextual bandits. Work in the literature has examined compression for distributed memoryless MABs (2), but only for rewards (scalar values) and not the contexts (large vectors), and thus these techniques also do not extend to our case.
Paper organization. Section 2 reviews our notation and problem formulation; Section and analyzes our algorithm for known and Section g for unknown context distributions.
3 provides
2 Notation and Problem Formulation
Notation. We use the following notation throughout the paper. For a vector X we use X; (X); to denote the i-th element of the vector X; similarly for matrix V, we use Vij or (V)ss to denote the element at row i, and column j. We use [|V||2 denote the matrix spectral norm. For a function f, we denote its domain and range by dom()). ran( respectively. When dom(f) C IR we use f(X) for a vector X E TRd to denote f(X) == dementtwwise for example
((x)),, i.e., the function f is applied use X2 to denote the element-wise square of X. We denote the inverse of a function f by f-1; if f is not one-to-one, with abuse of notation we use f to denote a function that satisfies f(f ((f))())) = xYvr E ran(f) (this is justified due to the axiom of choice (22). ). For matrix V. we use V-1 to denote its inverse; if V is singular, we use V-1 to denote its pseudo-inverse. We use [N] for N E N to denote ..,, N). and Aa to denote the set {aa, Xa)la E A). We say that y = (z)) if there is xp and a constant C' such that S Cf(x) VX > Io; we also use (()())) to omit log factors.
Contextual Linear Bandits. We consider contextual linear bandits problem a horizon of length T M where at each iteration = 1..,, T, an agent, taking into account the context, chooses an action de A and receives a reward r,, For each action a A, the agent has access corresponding feature vector Xt, E Rdd The set of all such vectors fXr.a is the context at time I, and the agent can use it to decide which action a, to play. We assume that the context is generated from a distribution, i.e., given a, Xe,a is generated from distribution Pa. As a specific example, we could have that a E IRd and Xe. is generated from a Gaussian distribution with zero mean and covariance matrix ||a|l2/, where I is the identity matrix, i.e., Pa = AO ||all24). The selection of a, may depend not only on the current context {X AasA but also on the history H, A [{X1.a) d1, (X.-1.a) 0t-1, (e-1), namely, all previously selected actions, observed contexts and rewards. Once an action is selected, the reward is generated according to
rt = (Xe, 0.) + Ti:
(1)
where (..-) denotes the dot product, 0, is an unknown (but fixed) parameter vector in Rdd and
Wh is noise. We assume that the noise follows an unknown distribution with E[yc|Fi, = 0 and
E Elexp(An) ) Fi] < exp(X2/2)VX E I, where F, o o(XX1a))aA 41, f1 .... (Xr,a)eeA a²) is the
filtration B of historic information up to time t, and (X) is the o-algebra generated by X [I3]
Our techniques could be adapted to additionally improve the communication efficiency of batched algorithms, but this is not the focus of our work.
3

---

The objective is to minimize the regret Rr over horizon of length T, where
T
RT =
( 0.) (Xt, 0.)
(2)
aeA
The best performing algorithms for this problem, such as LinUCB and contextual Thompson sampling.
achieve a worst case regret of (dv/T) 29 28 2 The best known lower bound ((dvT) (67
In the rest of this paper, we make the following assumptions that are standard in the literature 24
Assumption 1. We consider contextual linear bandits that satisfy: (1.) ||X2, S 1, VI E [T], E A.
(2.) ||0~112 1. (3.) r. E [0, 14 E (T).
The boundedness assumption on ry can relaxed using bits average to send rt, even if it is unbounded.
21 which only requires approximately 3.5
Memoryless Distributed Contextual Linear Bandits. We consider a distributed setting that consists of a central learner communicating with geographically separated agents. For example, the agents are drones that interact with traffic policeman (central learner) as they fly by. We assume that the agents do not keep memory of past actions and may not be present for the whole duration of learning; learning in our setup can happen thanks to the persistent presence of the central learner.
At each time f, t = 1... T, a distributed agent joins the system; she receives from the central learner information on the system, such the current estimate of the parameter vector 0, or the history Hy; she observes the current context {Xta) selects and plays an action Or and collects the corresponding reward r,. Note that although the distributed agent knows the context ) the action and the observed reward the central learner does not. The central learner may need this information to update its estimate of the system parameters, such as the unknown parameter vector 0,, and the history H However, we assume that the agent is restricted to utilize a communication- constrained channel and thus may not be able to send the full information to the central learner.
The main question we ask in this paper is: can we design a compression scheme, where the agent sends to the central learner only one message using B, bits (for small possible value of B,) that enables the central learner to learn equally well (experience the same order of regret) as if there were no communication constraints? With communication constraints the agent could send unquantized the full information {{ ((xr,a J 4z, r.). Instead, the agent transmits a message that could be a function of all locally available information at the agent. For example, it could be a function of (He, {Xe.e, JoEAA (t,Te). Tt), if the agent had received H, from the central learner. It could also be function of just (Xi, T2), which could be sufficient if the central learner employs an algorithm such as LinUCB N 37 In summary, we set the following goal.
Goal. Design contextual linear bandit schemes for the memoryless distributed setting that achieve the best known regret of Odd (Tlo(())) while communicating small number of bits B,.
We only impose communication constraints on the uplink communication (from the agents to the central learner) and assume no cost downlink communication (see discussion in Secttion D.
Stochastic Quantizer (SQ) [6 Our proposed algorithms use stochastic quantization, that we next review. We define SQ,, E E N to be a quantizer, that uses log(E + 1) bits, consisting of an encoder and decoder described as following. The encoder & takes value [0, E and outputs an integer value
with probability [x] with probability x [x]
Ee
(3)
The output & is represented with log(A + 1) bits. The decoder Dj takes as input the binary repre- sentation of (x) and outputs the real value Ee(z). The composition of the encoder & the binary mapping. and decoder De is denoted by SQ.. We notice that since the decoder only inverts the binary mapping operation, we have that SQ = &e. When SQ& is applied at the agents side, the agent encodes its data, as & (z). then sends the corresponding binary mapping the central learner that applies De to get (z). With slightly abuse of notation, this operation is described in the paper, by saying that the agent sends SQe to the central learner.
The quantizer SQ is a form of dithering 16 and it has the following properties
[x)]a = |x| [x][[]] x) + [x [x]) x[[x]
[x]) x, and
(QQ(2)) z| S

---

In particular, it conveys an unbiased estimate of the input with difference that is bounded by 1 almost surely. We also define generalization of SQ, denoted by SQ! where the input x of the encoder is in (a, bj instead of [0, f.. The encoder first shifts and scales using ã مーر (z - a) to make it lie in [0, f]. then feeds F to the encoder in This operation is inverted at the decoder. is
easy to see that SQ (a.b] satisfies
E[SQ la. (-)]a] = x, |sO| Asolum (x) x S b-a
3 Contextual Linear Bandits with Known Context Distribution
In this section, we show that if the central learner knows the distributions for the vectors xt.a then the agent does not need to convey the specific realization of the vector Xr,. e she observes at all - it is sufficient to just send 1 bit to convey some information on the observed reward and nothing else. But for this very limited communication, the central learner can experience the same order regret, when receiving in full precision all the information that the agents have, namely, Ry = O(d/T log T). Algorithm [ that we describe in this section, provides method to achieve this. Algorithm is clearly optimal, as we cannot hope to use less than zero bits for the vector Xt,a-
Remark 1. Knowledge of the distribution of Xt.a is possible in practice, since many times the context may be capturing well studied statistics (e.g., male or female, age, weight, income, race, dietary restrictions, emotional state, etc) the advent of large data has made and will continue to make such distributions available. Similarly, actions may be finite (eg., restaurants to visit) or well described (e.g., released amounts of substances), and thus the distribution of Xt,a could be derived. When the distribution is approximately known, we provide later in this section a bound on the misspefication performance penalty in terms of regret.
Main Idea. The intuition behind Algorithm I is that it reduces the to a single context problem. In particular, it calls as a subroutine an algorithm we term A, that serves as placeholder for any current (or future) bandit algorithm that achieves regret O(d/T log T)) for the case of a single context (for example, LinUCB 11 (7). The central learner uses A to convey to the agents the information they need to select a good action. Our aim is to parametrize the single context problem appropriately, so that, by solving it we also solve our original problem.
linear bandit problem
Recall that in single context problem, at each iteration t, any standard linear bandit algorithm A selects a feature vector (an action) xa from a set of allowable actions X, and observes a reward
(z), T).
where 6¹, is an uknown parameter and 77 is noise that satisfies the same assumptions as in T. The objective of A is to minimize the standard linear regret (A) over horizon of length T. namely
(5) Our reduction proceeds as follows. We assume that A operates over the same horizon of length T and parametrized by an unknown parameter 6', We will design the action set X that we provide to using our knowledge of the distributions P. as we will describe later in (7). During each iteration, the central learner asks A to select an action H, E X' and then provides A reward for this action (our design ensures that this reward satisfies 4 with 6 0-). A operates with this information, oblivious to what else the central learner does. Yet, the action x, is never actually played: the central learner uses the selected action &e to create an updated estimate of the parameter vector ò., as we will describe later, and only sends this parameter vector estimate the distributed agent. The agent observes her context, selects what action to play, and sends back her observed quantized reward to the central learner. This is the reward that the central learner provides to A. We design the set X' and the agent operation to satisfy that: 4 holds; and Rr - RT((A is small, where Ry is the regret for original multi-context problem and Ry (A) the regret of A. We next try to provide some intuition on how we achieve this.
(A) Σt= max (z, 0.) 61).
We first describe how construct the set X. Let O be the set of all values that 0, could possibly take. For each possible parameter vector value 0 E O the central learner considers the quantity
x (8) = E [a -. P.) Jarg max #c ()(
(v.
(6)
Recall that given a, Xt.a is generated from distribution Pa. see Section 2
5

---

Intuitively, for each value of 0, we optimistically assume that the distributed agent may select the best possible realization Xt,a for this 9 (that has the expectation in (6), and receive the associated reward; accordingly, we restrict the action space X' of to only contain the expectation of these "best" Xt.a- where is the random variable that follows the distribution Pa. Ties in 6 can be broken uniformly random. fact any pre-selected choice function would work as long as the same function is also used in step 12 of Algorithm 1 Note that the function X Rd IR can be computed offline before
the learning starts, see Example We then use
X' (X'(00
The vector by E X' may not actually be the vector corresponding the action the agent selects; it is only used convey to the agent an estimate of the unknown parameter O, that satisfies x₁ x (O.). Although the central learner does not control which action the agent plays, this is influenced by 05: we show in App. that Xt,e, is an unbiased estimate of Tt, and the generated reward follows the linear model in with 0' = -.. In Theorem we prove that
arg max 0.) (6.). xEX'
Hence, if A converges to selecting the best action for the single context problem, we will have that & converges 0. if the maximizer in (8) is unique. If there are multiple values for 0 with X (8) = (6.), we show in the proof of Theorem | that they all lead to the same expected reward for the original multi-context problem.
(1,2). Xt. E (-1,1) Va E = = 0, and X takes the value 1 with probability p and otherwise, while X1,2 takes the values
Example 1. Consider the case where d
-1 with probability and otherwise. Then, we have that
arg max (Xr,a) 1) - -1 Xt,a
{
1
with probability 1-P4 with probability pq.
where we use the fact that if arg maxx,,, (Xt,as 1) + 1, it must be the case that both Xx,1 and
Xx,2 1. Thus, (1) Elarg maxx, x.. (Xr,a 1)] 1 2pg. and similarly X*(-1) -1+ 2(1 p) 9), and hence, X' {1 2pq. 11 2(1 10--p0 p) 9)}. If A decides pick
J₁ 1 -2pg. we have that 0, otherwise 0, 11 This estimate O, is then conveyed to the
agent to help her pick the action.
Algorithm Operation. The pseudo-code is provided in Algorithm 1
First, the central learner calculates the function
(+) P.. (arg
(x, 0}]
(10)
()
and creates the action set X' (X)(0) E Q} that algorithm A is going to use.
At each time I, based on past history, decides on a next action xa E X. The central learner uses
I₁ to calculate the new update 0, = x (xx),, where X-1 is the inverse of X (see Section 2).
The agent receives Ú, from the central learner, observes her context, plays an action
arg m (X dz). and observes the reward rt. She then quantizes the reward using stochastic quantizer SQ1 (see Section 2 and communicates the outcome using one bit to the central learner.
The central learner provides the quantized reward as input to A. Note that A is oblivious to what actions are actually played: it treats the received reward as correspondigg to the action 2, it had decided.
The following theorem proves that Algorithm| achieves a regret RT + O( O(VTlog T), where (A) is the regret of A in (5. Hence, if A satisfies the best known regret bound of Od T), e.g., LinUCB, Algorithm I achieves a regret of Odd/Tlog T). The thcorem holds under the mild
set of assumptions that we stated in Section 2
Theorem 1. Algorithm uses 1 bit per reward and 0 bits per context. Under Assumption achieves a regret RT (A) + O(VT log T)) with probability at least 1- 4.
! it
The complete proof is available in App. A the definition of X* in 10),, we notice the following. Recall that the distributed agent receives d from the central learner, and pulls the best action for this 0,, i.c., as arg max (X Qt). We
Proof outline.
We next provide a short outline. From

---

Algorithm 1 Communication efficient for contextual linear bandits with known distribution
1: Input: an algorithm A for one context case, underlying set of actions X. and time horizon T.
2: Initialize: (0) = (e......PP. (arg (EEA) 0)), X {X* (0)( 0 fo 0.
3: Let X be inverse of X*.
4: for t= 1 II' do
5: Central learner:
6:
Receive F--1 and provide it to A.
7:
A, using the history (#1, fI...., Ft- R2-1), selects zt.
8:
Send 8, = X (xz) to agent.
9:
Agent:
Receive Ú, from the central learner. Observe context realization far.a
11:
12:
Pull arm d₃ arg maXae (X 0t) and receive reward Send f. = SQ, (Tt) to the central learner using 1-bit.
13:
show that conditioned on Fy, the associated vector Xt,a, is an unbiased estimate of a with a small variance. Given this, prove that 4 satisfies (6) and thus the rewards observed by A are generated according to a linear bandit model with unknown parameter that is the same as 0..
We next decompose the difference RT RT(AA to two terms: St=i(arg maxx,,, (x),00))00.)
Σx
(0r, and Ei/ Σt= (arg maxx... (X (Xr,;;0),00) max 0.). To bound the first term, show that the unbiasdness property together with Assumption I implies that Er is a martingale with bounded difference. This im- plies that |Er O(VTlogT) with high probability. To bound Σ/, first show that arg max 0.) = (0.) (we note that this why the algorithm converges to Qg that equal to, or results in the same expected reward as, f.). Then, following a similar approach, we can show that 27, is a martingale with bounded difference which implies that |>1 = OlvTlog with high probability.
Downlink Communication. The downlink cost of our scheme (dd) (see App. A for discussion).
Operation Complexity. The main complexity that our algorithm adds beyond the complexity of
A, is the computation of the function X The time-complexity of (0) depends the context distribution. While computing (+) can be computationally expensive in worst-case scenarios, be computed/approximated efficiently for many practical distributions even in closed form. We give the following examples:
For d 0 > 0, we have that (0) is the expectation of the maximum of multiple random variables, i.e., (0) = Ex,-P, [max.e.4 KoJ. which can be computed/approximatee efficiently the distributions Pa are given in closed form.
If (Palaed are continuous distributions, then X (0), 0 * can be expressed
x0) =00)=- a'A (x (Ia: 0a # alIxaddP.. "EA zomPa
(11)
For many distributions, the previous expression be computed/approximated efficiently. For instance, consider the case where 2 1, xa are independent, identically distributed d-dimensional Gaussian vectors with mean μ and covariance matrix Σ U DU, where D is diagonal matrix is equal to (Q( (z. (z.-).0) | ))-- where Q(c)
and U upper triangular. The expectation
v2= Se exp( 2 drz. Hence, (0) can be approximated efficiently in that case.
For discrete distributions, (0) can be computed efficiently depending on the number of mass points of the distribution and the distribution has structures/properties to simplify the expression.
Imperfect Knowledge of Distributions. Since we only use the distributions to calculate X*, imperfect knowledge of distribution only affects us in the degree that it affects the calculation of X Suppose that have estimate X of X that satisfies
sup X (0) X (0)
(12)
7

---

Using Theorem I we prove in App. A the following corollary.
Corollary 1. Suppose are given X that satisfies 12 Then, there exists algorithm A for
which Algorithm achieves Rr- = OddVT eT' Vd) with probability at least 1 7.
Privacy. Our result may be useful for applications beyond communication efficiency; indeed, the context may contain private information (e.g., personal preferences, financial information, etc); use of our algorithm enables to not share this private information at all with the central learner, without impeding the learning process. Surprisingly, work in 48 motivated from privacy considerations, has shown that if an agent adds a small amount of zero mean noise to the true context before sending it to the central learner, this can severely affect the regret in some cases and yet our algorithm essentially enables to "guess" the context with no regret penalty if the distributions are known. Although adding a zero mean noise to the observed feature vector conveys an unbiased estimate of the observation, the difference between this and our case is technical and mainly due to the fact that the unbiasdness is required to hold conditioned on the central learner observation (noisy context).
Note that we do not make formal privacy claims in this paper, but simply observe that our approach could potentially be leveraged for privacy purposes. It is true that the reward can reveal some information about the context, e.g., if all the actions result in small reward for context and large reward for another context. However, privatizing the reward (which implies private context in our case) is much easier than privatizing the context and there are many proposed optimal algorithms with little no regret loss, e.g., see (20 38 44 35 This is not the case when privatizing the context. In
fact it was shown in [42] that privatizing the context can lead to linear regret and relaxed definitions of privacy are proposed to avoid this.
4 Contextual Linear Bandits with Unknown Context Distribution
We now consider the case where the learner does not know the context distributions, and thus Algorithm [ that uses zero bits for the context cannot be applied. In this case, related literature which is discouraging since it is probably impossible to establish an algorithm with communication logarithmically depending on Additionally, in practice we use 32d bits to convey full precision values- thus this conjecture indicates that in practice we may not be able to achieve order improvements terms of bits communicated, without performance loss.
conjectures lower bound of (d)) 46 !7
In this section, we provide Algorithm 2 that uses RJ 5d bits per context and achieves (optimal) regret RT = O log T). We believe Algorithm 2 is interesting for two reasons: 1. In theory, we need an infinite number of bits to convey full precision values- we prove that a constant number of bits per dimension per context sufficient. Previously best-known algorithms, which rely on constructing nne for the set of feature vectors, use O(d log T) bits per context, which goes to infinity as T goes to infinity. Moreover, these algorithms require exponential complexity 24 while ours is computationally efficient.
In practice, especially for large values of d, redueing the number of bits conveyed from 32d to = 5d is quite significant- this is reduction by a factor of six, which implies six times less communication.
Main Idea. The intuition behind Algorithm is the following. The central learner is going to use an estimate of the d x d least-squares matrix Vn2 = = Xi,,, i,a update her estimates for the parameter vector 6., Thus, when quantizing the vector Xt we want to make sure that not only this vector is conveyed with sufficient accuracy, but also that the central learner can calculate the matrix Vi accurately. In particular, we would like the central learner to be able to calculate an unbiased estimator for each entry of Xt,a and each entry of the matrix Vz. Our algorithm achieves this by quantizing the feature vectors X and also the diagonal (only the diagonal) entries of the least squares matrix Vt. We prove that by doing so, with only 5d bits we can provide an unbiased estimate and guarantee an O Va) quantization error for each entry in the matrix almost surely.
Quantization Scheme. We here describe the proposed quantization scheme.
To quantize Xt,,, Let m & [vd]. We first send the sign of each coordinate of Xt.a, using d bits, namely, we send the vector s; = Xxt,a/|Xr,,a. I. To quantize the magnitude ax we scale each coordinate of axr,a by m and quantize it using a Stochastic Quantizer (SQ with mn + 1 levels in
2 As described in in Section 2 SQ maps value x to an integer value, namely [x]] with probability [x] -
and [2] with probability
8

---

the interval [0, ml. Let X, - SQ (m| 1) denote the resulting SQ outputs, we note that X, takes non-negative integer values and lies in norm-1 ball of radius 2d (this holds since the original vector lies in norm-2 ball of radius 1 and the error in each coordinate is at most 1 //m). That is, it holds that
X, E Q = {I E || I 2d}. We then use any enumeration h Q + [[]] of this set to encode X₁ using log(1 bits.
To quantize "1aa Let Xi,a, denote vector that collects the diagonal entries of X X7,a L,as" Let X, - &t.,./m be the estimate of Xt,a, that the central learner retrieves. Note that X? is not an unbiased estimate of X2, however, (X {) ) S 3/m for all coordinates i (proved in B Our scheme simply conveys the difference X X? with bit per coordinate using a 3/ml
App.
SQ
quantizer.
The central learner and distributed agent operations are presented Algorithm 2
Example 2. Consider the case where d = 5. Then each coordinate of [ is scaled by 3 and quantized using SQ3 one the values 0, 2, 3 to get Xx, The function h then maps the values for X, that satisfy the X S 10 to unique value (a code) in the set [[Q]]. For instance the value 3.1 not given a code, where is the vector of all ones. However, note that for ( to be mapped to 3.1, we must have (1(X,,aj) t,, )al 2 2 for all coordinates i, which cannot happen since it implies that || 112 2 5/6 which contradicts Assumption
Algorithm 2 Communication efficient for contextual linear bandits with unknown distribution
1: Input: underlying set of actions A. and time horizon T.
2: 6o = 0, Vi = O, 0, m [vd].
3: Let h be an enumeration of the set Q = far E | S 2d).
4: for = =1:7 7 do
5:
Agent:
6:
Receive Ô_-1 from the central learner.
7:
Observe context realization {Xr,aJasA
8:
Pull arm ag = arg ( b(-1) and receive reward rz.
9:
Compute the signs 8, X Xx, Xx,a,l of Xt,as
10:
Let X, = SQ,,. (ml l)
et 10oo3//mmmmmm//mm 13/333m,33 3//mm33/ml (X2 - X²), where X, stXi/m.
12:
Send to the central learner (X,),, 8t, and es using log, (12() d, and bits, respectively.
13:
Send A. (re) using 1-bit.
14:
Central learner:
15:
Receive Xx, St. ef, and P. from the distributed agent.
X. = 8.X./m, X(D) X? ee.
17:
ut t- u-1 + P.X..
V. V.11+ +XXT (x, + diag( (x:)))
18:
0, + V
20:
Send B, to the next agent.
Algorithm Performance. Theorem 2 stated next, holds under Assumption I in Section 2 and some
additional regulatory assumptions the distributions Pa provided in Assumption Assumption 2. There exist constants c, c' such that for any sequence o,,.... 0r, where 8 depends only on He, with probability at least 1 - $ it holds that
E'=1 X,,, 2 I E
(13)
where = arg maxae
(Xt,, (Xt,a, Oz), and I is the identity matrix.
We note that several common assumptions in the literature imply (3). for example, bounded eigenvalues for the covariance matrix X,,.. [I] 27 Such assumptions hold for a wide range of distributions, including subgaussian distribitions with bounded density 36
Challenge relaxing assumption (diversity assumption). The main challenge in relaxing the diversity assumption for LinUCB (or Thompson sampling) based algorithms is that the regret of those
2

---

algorithms is bounded as Ó(VT 0=llv;). Without quantization, the quantity ||0r 0- llvr grows slowly and is nearly a constant; however, without the diversity assumption, the quantization error can make |Ør - 0- L to grow as vT in the worst case. This is due to the fact that sub-optimal arms do not have large number of pulls, hence, we do not have good estimate of O, on those direction; on the other hand, the quantization errors in estimating Vr is accumulated in all directions. As a result, the regret bound increases by a factor of T1/11 We leave it as a future work to either relax the diversity assumption (which is required in our paper only in the case of unknown context distribution) or else show that removing it will unavoidably increase the regret order.
Theorem 2. Algorithm satisfies that for all t: X, E Q; and B, S + logg + 1) + 5.03d bits. achieves regret Ry = O(dvTlog T) with probability at least 1 7-
Under assumptions 7
Proof Outline. To bound the number of bits B,, we first bound the size of Q by formulating a standard counting problem: we find the number of non-negative integer solutions for a linear equation. To bound the regret li, we start by proving that our quantization scheme guarantees some desirable properties, namely, unbiasedness and O Va
{+)
quantization error for each vector coordinate. We then
upper bound the regret in terms of |10, 0- 02112 and show that this difference can be decomposed as
[l. - 0-112 - VV,VV E Eill2 + (1 + InDI e:112 + + ixXi,,,12
(14)
where Eg captures the error in estimating the matrix Xt,a, XT,a,, is the error in estimating Xt.a,, and v/ is noise that satisfies the same properties as l/. Using Assumption 2 we prove that V, grows as O()) with high probability, and from the unbiasdness and boundedness of all error quantities show
that they grow as O(vilog () with high probability. This implies that ||0, - 0-112 = Odd log
and hence, R = ((dd/Tlog' The complete proof is provided in App. B
Algorithm Complexity. If we do not count the quantization operations, it is easy to see that the complexity of the rest of the algorithm is dominated by the complexity of computing V,-1 which can be done in O(d2.373) 4. For the quantization, we note that each coordinate of X₁ can be computed in Ó(1 time Moreover, the computation of h2z) for E Q can be done in constant time with high probability using hash tables, where h is the enumeration function in Step 3 Hence, the added computational complexity is almost linear in d. Although a hash table for h can consume (2(2dd) memory, by sacrificing a constant factor in the number of bits, we can find enumeration functions that can be stored efficiently. As an example, consider the scheme in [4] that can find an one-to-one function h Q - N+ which can be stored and computed efficiently, but only gives guarantees in expectation that [loo(((())) = (d) for all x E Q.
Downlink Communication Cost. Although we assume no-cost downlink communication, as was also the case for Algorithm | the downlink in Algorithm 2 is only used to send the updated parameter vector 6, to the agents. If desired, these estimates can be quantized using the same method as for Xt.o.. which (following similar proof to that of Theorem can be shown to not affect the order of the regret while reducing the downlink communication to 5d bits per iteration.
Offloading To Agents. For applications where the agents wish to computationally help the central learner, the central learner may simply aggregate information to keep track of u4, V, and broadcast these values to the agents; the estimate 0g can be calculated at each agent. Moving the computational load to the agents does not affect the regret order or the number of bits communicated on the uplink.
Remark 2. Under the regulatory assumptions in 17 the regret bound can be improved by factor of / //lg(K)) (/d,, where K |A] is the number of actions. However, this does not improve the regret in the worst case as the worst case number of actions is O(C*), C >
Societal Impact. Results in this work can be used in decision making systems which can potentially lead to biased decisions against racial, sex, or minority groups if used without care.
Acknowledgment. CF and OH are supported in part by NSF award 2007714, NSF award 2221 1221871 and Army Research Laboratory grant under Cooperative Agreement W911NF-17-2-019. LY is supported in part by DARPA grant HR001 12190130, NSF Award 2221871.
'Multiplication by vd can take Olog d) time.
10

---

References
[1] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] S. Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference machine learning, pages 127-135. PMLR, 2013.
[3] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. Qsgd: Communication- sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30, 2017.
[4] J. Alman and V. V. Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 202/ ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522- 539. SIAM, 2021.
[5] A. Anandkumar, Michael, A. K. Tang, and Swami. Distributed algorithms for learning and cognitive medium access with logarithmic regret. IEEE Journal on Selected Areas in Communications, 29(4):731-745 2011.
[6] V. Anantharam, P. Varaiya, and J. Walrand. Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-part i: lid rewards. JEEE Transactions on Automatic Control, 32(1 0:968-9766 1987.
[7] M. H. Anisi, G. Abdul-Salaam, and A. H. Abdullah. A survey of wireless sensor network approaches and their energy consumption for monitoring farm fields in precision agriculture. Precision Agriculture, 16(2):216 2015.
[8] Auer. Using confidence bounds for exploitation-explorrtion trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
[9] B. Awerbuch and R. D. Kleinberg. Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 45-53, 2004.
[10] D. Bouneffouf, I. Rish, and G. A. Cecchi. Bandit models of human behavior: Reward processing in mental disorders. In International Conference on Artificial General Intelligence, pages 237- 248. Springer, 2017.
[11] Q. Ding, C.-J. Hsich, and Sharpnack. An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling. In International Conference Artificial Intelligence and Statistics, pages 1585 1593. PMLR, 2021.
[12] A. Durand, C. Achilleos, D. Iacovides, K. Strati, G. D. Mitsis, and J. Pineau. Contextual bandits for adapting treatment mouse model de novo carcinogenesis. In Machine learning for healthcare conference, pages 67-82. PMLR, 2018.
[13] R. Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
[14] P. Elias. Universal codeword sets and representations of the integers. IEEE transactions on information theory, 2442)1194-203 1975.
[15] A. Gersho and R. M. Gray. Vector quantization and signal compression, volume 159, Springer Science Business Media, 2012.
[16] R. M. Gray and T. G. Stockham. Dithered quantizers. IEEE Transactions on Information Theory, 39(3):805-88) 812, 1993.
[17] Y. Han, Z. Zhou, Z. Zhou, J. Blanchet. P. W. Glynn, and Y. Ye. Sequential batch learning in finite-action lincar contextual bandits. arXiv preprint arXiv:2004.0633 2020.
[18] O. A. Hanna, Ezzeldin, C. Fragouli, and Diggavi. Quantization of distributed data for learning, IEEE Journal on Selected Areas in Information Theory, 2(3):987-1001, 2021.
11

---

[19] O. A. Hanna, Y. H. Ezzeldin, T. Sadjadpour, C. Fragouli, and S. Diggavi. On distributed quantization for classification. IEEE Journal on Selected Areas in Information Theory, 1(1):237~ 249, 2020.
[20] O. A. Hanna, A. M. Girgis, Fragouli, and S. Diggavi. Differentially private stochastic linear balmoss)) for free. arXiv preprini arXiv:2207.03445, 2022.
[21] O. A. Hanna, L. Yang, and C. Fragouli. Solving multi-arm bandit using a few bits of communi- cation. In International Conference Artificial Intelligence and Statistics, pages 11215-11236 PMLR, 2022.
[22] T. Jech. The axiom of choice. Courier Corporation, 2008.
[23] P. C. Landgren. Distributed multi-agent multi-armed bandits. PhD) thesis, Princeton University, 2019.
[24] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[25] T. Le, Szepesvari, and R. Zheng. Sequential learning for multi-channel wireless network monitoring with channel switching costs. IEEE Transactions on Signal Processing, 62((2):5919- 5929, 2014.
[26] F. R.L.D, D. Yu, H. Yang, J. Yu, H. Karl, and X. Cheng. ing algorithms in wireless networks: A survey. IEEE Wireless Communications, 27(1))24-30, 2020.
spectrum schedul-
[27] L. Li, Y. Lu, and D. Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference Machine Learning, pages 2071-2080. PMLR, 2017.
[28] Y. Li, Y. Wang, X. Chen, and Y. Zhou. Tight regret bounds for infinite-armed linear contextual bandits. In International Conference on Artificial Intelligence and Statistics, pages 370-378. PMLR, 2021.
[29] Y. Li, Y. Wang, and Y. Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pages 2173-2174. PMLR, 2019.
[30] Mary, R. Gaudel, and P. Preux. Bandits and recommender systems. International Workshop Springer, 2015.
on Machine Learning. Optimization and Big Data, pages
[31] Matikainen, M. Furlong, Sukthankar, and M. Hebert. Multi- armed recommendation bandits for selecting state machine policies for robotic systems. In 2013 IEEE International Conference on Robotics and Automation, pages 4545-4551. IEEE, 2013.
[32] P. Mayekar and H. Tyagi. Ratq: A universal fixed-length quantizer for stochastic optimization. In International Conference on Artificial Intelligence and Statistics, pages 1399-1409. PMLR, 2020.
[33] T. D. Novlan, H. S. Dhillon, and J. G. Andrews. Analytical modeling of uplink cellular networks. IEEE Transactions on Wireless Communications, 12(6):2669-266 2679, 2013.
[34] A. N. Rafferty, H. Ying, and J. Williams. Bandit assignment for educational experiments: Ben- efits to students versus statistical power. In International Conference on Artificial Intelligence in Education, pages 286-290. Springer, 2018
[35] W. Ren, X. Zhou, J. Liu, and N. B. Shroff. Multi-armed bandits with local differential privacy. arXiv preprint arXiv:2007.03121, 2020.
[36] 7. Ren and Z.. Zhou. Dynamic batch learning in high-dimensional sparse linear contextual bandits. arXiv preprint arXiv:2008. / 1918, 2020.
[37] Rusmevichientong and J. N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 351
12

---

[38] т. Sajed and O. Sheffet. An optimal private stochastic- mab algorithm based on optimal private stopping rule. In International Conference on Machine Learning, pages 5579-5588. PMLR, 2019.
[39] S. Sajeev, J. Huang, N. Karampatziakis, M. Hall, S. Kochman, and W. Chen. Contextual bandit applications in a customer support bot. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 3522 3530, 2021.
[40] F. Seide, H. Fu, J. Droppo, G. Li, and D. Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association. Citeseer, 2014.
[41] Shahrampour, A. Rakhlin, and A. Jadbabaie. Multi-armed bandits in multi-agent networks. In 20/7 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2786 2790.. IEEE, 2017.
[42] R. Shariff and O. Sheffet. Differentially private contextual linear bandits. Advances Neural Information Processing Systems, 31, 2018.
[43] C. Shi and C. Shen. Federated multi-arme' bandits. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021.
[44] J. Tenenbaum, H. Kaplan, Y. Mansour, and U. Stemmer. Differentially private multi-armed bandits in the shuffle model. Advances in Neural Information Processing Systems, 34:24956- 24967, 2021.
[45] M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[46] Y. Wang, J. Hu, X. Chen, and L. Wang. Distributed bandit learning: Near-optimal regret with efficient communication. In International Conference on Learning Representations, 2019.
[47] Y. Zhang. J. Duchi, M. I. Jordan, and M. J. Wainwright. information-thcoretio lower bounds for distributed statistical estimation with communication constraints. Advances in Neural Information Processing Systems, 26, 2013.
[48] K. Zheng, T. Cai, W. Huang, 7. Li, and L.. Wang. Locally differentially private (contextual) bandits learning. Advances in Neural Information Processing Systems, 33:12300-12310, 2020.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Theorem and Theorem 2
(b) Did you include complete proofs of all theoretical results? [Yes] See App. and App.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi-
mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "j3zfT0kdni5", "reviewer": "Reviewer_XFw3", "summary": "This paper studies contextual linear bandits with communication constraints, where it is desired to transmit as few number of bits as possible from the agent to the learner. The authors considered two different settings, i.e., the learner knows the distribution of contexts, and the learner doesn’t know the distribution of contexts, respectively. For the former case, the authors proposed an interesting reduction method that converts the original bandit problem with time-varying candidate set (multiple contexts) on the agent side to one with fixed candidate set (one context) on the learner side, so that there is no need to spend any bits on the contexts. For the latter case, the authors proposed an algorithm that quantizes the context with 5d bits via a stochastic quantizer. The authors proved that the proposed algorithms match the regret of standard contextual linear bandit algorithms.", "questions": "I am not sure if distributed contextual linear bandits a suitable title, as in this paper, learning only happens on the central learner, while the distributed agents are only responsible for pulling arms and compress the required messages. This is very different from the existing works in distributed contextual bandits, where each agent usually maintains its own model estimate.\n\nThe terms used for the agents in this problem should be made more consistent. Currently, we have \"central agent\", \"central learner\", and \"learner\" all referring to the same thing.\n\nI am also a bit confused about the discussion about provacy in line 278. It is true that the proposed algorithms avoid directly sending context vectors, but isn't sending $\\hat{\\theta}$ also reveals private information, considering it will eventually converge to the true parameter $\\theta_{\\star}$.", "limitations": "No", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well written and easy to follow for the most part.\nThe proposed algorithm for the setting with known context distribution seems novel, and the technique may be useful for other related problems. \nRecently there is an increasing number of works in distributed bandit learning that tries to minimize the total number of communication rounds needed in the time horizon. In comparison, this work aims to minimize the bits required for each round, so it may help further improve communication efficiency in a parallel direction.\n\nMy main concern is about the motivation for the current formulation.\n\nAs mentioned in introduction, the agents are assumed to be transient and \"they may not be interested in learning - this may not be a task that the agents wish to consistently perform - and thus do not wish to devote resources to it\". However, in the algorithm design, these agents still need to be cooperative, in the sense that they are required to perform computations to compress and communicate the required messages to help the learner, e.g. line 6-13, even though it will not benefit them at all.\n\nMaybe I am missing something here. Why the focus is only put on the compression of context, while it is okay to transfer the uncompressed \\hat{\\theta}? For both algorithms, the learner still needs to send the uncompressed \\hat{\\theta} to the agent, which has the same dimension as the context vector for an arm, which is also communication expensive.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fYGTi2sdh4b", "reviewer": "Reviewer_iMrk", "summary": "This paper considers the contextual bandit with limited communication. In this problem, each arm has a context distribution and a context at each round t=1,2,...,T is iid from the corresponding distribution. The goal is to learn the coefficient theta* to choose the arm of the largest reward rti = <Xti, theta_*> + eta_t, where eta_t is an iid noise. For ease of discussion, all contexts and theta_* lie in a unit ball. It is well-known that UCB and Thompson sampling algorithms are effective in this setting. Each agent receives the estimated theta from the central learner, chooses an arm, and sends information to the learner. Regarding the learner's ability, this paper considers two settings: First setting is that the learner knows the context distribution. The second setting is that the learner does not know the context distribution. \n\nAlgorithm 1 for the first setting sends 1-bit information that suffices to have optimal sqrt{T log T} rate. Algorithm 2 for the second setting sends 5d-bit information and has the optimal rate. \n\nThis paper is mostly well-written. The introduction of algorithms can be improved. For example, Line154-160 and L194-206 are not very helpful before I actually see the algorithm with example. I feel the results somewhat lack integration (for example, alg 1 is black-box whereas alg 2 is base algorithm dependent), but overall the results are slightly above the bar.\n\nDetails:\n\nAlgorithm 1 is a meta-algorithm that internally uses the standard bandit algorithm \\Lambda. The crux in this part is that, if the algorithm sends the agent hattheta_t = X^{-1}(xt), then the average context is xt and the 1-bit signal is an unbiased estimator of rt = <xt, theta>. Since agents never send contextual information to the learner, this algorithm depends on the context distribution, but some remedy is discussed in Line272-274.\n\nAlgorithm 2 is an algorithm that sends partial information about the contexts. The algorithm carefully quantifies contexts. Note that if several terms are multiplicated in the update formula, the composite terms also need to be quantified. It assumes that every path of arms linearly increases each eigenvalue and the exploration-exploitation tradeoff is not seriously dealt.\n\nThe model depends on the assumption that rt is bounded, and extending it to Gaussian bandits is plausible.\n", "questions": "* Is the computational complexity of alg 1 addressed?\n* Is it possible to analyze incorrectly specified context distribution?\n* Can we make algorithm 2 black-box?\n* What happens when the minimum eigenvalue is not guaranteed to grow in algorithm 2?\n* Is there any justification for the limited uplink communication while allowing unlimited downlink communication?", "limitations": "I found no ethical problem. \nAlgorithm 2 omits the exploration-exploitation tradeoff, but is okay for the conceptual idea for these results.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nElegant setup and algorithms.\nrobustness to the estimation error of context distribution.\n\nWeaknesses:\nInpractical settings (unlimited downlink communication).\nInsufficient discussion on the operation complexity of obtaining X^*(theta) and its inverse (alg 1).\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3qh959SQRb4", "reviewer": "Reviewer_y1xV", "summary": "This paper studies a distributed linear bandit setting with a central learner and agents that observe contexts and execute decisions. As the central learner does not observe the context, each agent needs to communicate its decision and observations. The goal of this paper is to minimize \"uplink\" communication, i.e. the number of bits each agents needs to transfer in order to enable central low regret learning. Two results are provided under different assumptions on the context distribution. The proposed solution is a reduction framework that leverages existing results on linear bandits.", "questions": "* How is (6) defined for parameters with multiple optimal actions? For instance at $\\\\theta = 0$, all actions are optimal, and the definition of $X^*(\\\\theta)$ depends on this choice.\n\n", "limitations": "* It is unclear if $X^*(\\\\theta)$ and its inverse can be computed. The provided example is for d=1, whereas d>1 will be relevant for many applications. This is discussed around 267-271, but I do not see that the authors provide a good resolution. This is potentially quite a big limitation of the method.\n\n* The regret bound for unknown contextual distribution requires a strong diversity assumption (Assumption 2). This allows the agents to essentially always play the greedy action. Without this assumption, the agents would need to engage in active exploration, and it is perhaps less clear how to coordinate this. A straightforward idea could be to use Thompson sampling, and communicate the sampled parameter to the agent.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Clarity:**\n\nOverall, the paper is well written. I have some minor remarks to further improve clarity:\n\n* line 66 and 300: Please discuss why previous works require O(d log(T)) bits and explain what is meant by \"exponential complexity\". Note that the reference [19] does not provide algorithms for the distributed setting, as far as I know.\n* line 91: Are two different notations needed for vector indices? Consider using only one.\n* line 120: The cited bounds are not quite correct; [1] achieves $d \\\\sqrt(T) \\\\log(T)$; [28] achieves $d \\\\sqrt(T) \\\\log(T)^{3/2}$; [2] achieves roughly $d \\\\sqrt{T \\\\log(K)}$ (which is a factor $\\\\log(K)$ worse). Moreover, these bounds are not the best known, see e.g. https://arxiv.org/abs/1904.00242 and https://arxiv.org/abs/1905.01435\n* below line 190: I find the notation $\\\\theta^*(\\\\Lambda)$ very confusing: Why is the unknown parameter a function of the algorithm?\n* line 216: It might hep to say that the agent plays the argmax action for $\\\\hat \\\\theta_t$!\n* line 220: In what sense do we have $\\\\theta_t = \\\\theta^*$? As written this is almost certainly not true.\n* Algorithm 1 / 2: Consider using the same ordering for central learner and agents in the pseudo code\n* Eq (14) in the appendix: Why do you introduce a conditioning on $\\\\theta^*$ in the expectation? $\\theta^*$ is not a random variable.\n\n**Quality:**\n\nThe assumptions and results are clearly stated. I liked that the main paper provides proof sketches. I spent some time checking the proofs in the appendix and did not identify any technical flaws.\n\n**Originality & Significance:**\n\nThis paper studies a well motivated setting. Related work is discussed. I am not an expert in distributed computation, but to me the ideas in the context of linear bandits are novel. \n\n**Minor:** \n\n* 191: typo in 'uknown'\n* 254: typo in 'unbiasdness'", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept