Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: This paper is well written and easy to follow for the most part.
The proposed algorithm for the setting with known context distribution seems novel, and the technique may be useful for other related problems. 
Recently 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.

My main concern is about the motivation for the current formulation.

As 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.

Maybe 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.

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.

The 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.

I 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
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: **Clarity:**

Overall, the paper is well written. I have some minor remarks to further improve clarity:

* 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.
* line 91: Are two different notations needed for vector indices? Consider using only one.
* 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
* below line 190: I find the notation $\\theta^*(\\Lambda)$ very confusing: Why is the unknown parameter a function of the algorithm?
* line 216: It might hep to say that the agent plays the argmax action for $\\hat \\theta_t$!
* line 220: In what sense do we have $\\theta_t = \\theta^*$? As written this is almost certainly not true.
* Algorithm 1 / 2: Consider using the same ordering for central learner and agents in the pseudo code
* Eq (14) in the appendix: Why do you introduce a conditioning on $\\theta^*$ in the expectation? $\theta^*$ is not a random variable.

**Quality:**

The 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.

**Originality & Significance:**

This 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. 

**Minor:** 

* 191: typo in 'uknown'
* 254: typo in 'unbiasdness'
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.


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.

* 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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 

Algorithm 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. 

This 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.

Details:

Algorithm 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.

Algorithm 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.

The model depends on the assumption that rt is bounded, and extending it to Gaussian bandits is plausible.

strengths_and_weaknesses: Strengths:
Elegant setup and algorithms.
robustness to the estimation error of context distribution.

Weaknesses:
Inpractical settings (unlimited downlink communication).
Insufficient discussion on the operation complexity of obtaining X^*(theta) and its inverse (alg 1).

questions: * Is the computational complexity of alg 1 addressed?
* Is it possible to analyze incorrectly specified context distribution?
* Can we make algorithm 2 black-box?
* What happens when the minimum eigenvalue is not guaranteed to grow in algorithm 2?
* Is there any justification for the limited uplink communication while allowing unlimited downlink communication?
limitations: I found no ethical problem. 
Algorithm 2 omits the exploration-exploitation tradeoff, but is okay for the conceptual idea for these results.
review_title: null

Meta-review: metareview: The reviewers are overall positive about the theoretical contributions of the paper, for which I share the same (generally) positive evaluation.
Please make sure you address all the reviewers' comments and incorporate them (and any new experimental results, if applicable) in your camera-ready.
confidence: Certain
Decision: Accept