Venue: NeurIPS 2022 Conference

Reviews:

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: The manuscript proposes a federated contextual linear bandit algorithm in the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents’ communication. The proposed algorithm obtains a near-optimal regret and low communication complexity. 
strengths_and_weaknesses: Strengths

(a) This is the first asynchronous federated linear contextual bandit model considering the following features: (i) Each agent can decide whether or not to participate in each round; (ii) The communication between each agent and the server is asynchronous and totally independent of other agents. 

(b) Considering that the order of the interaction between the agent and the environment is not fixed, standard martingale-based concentration inequality cannot be directly applied. This work applies a novel proof technique to solve this issue, which could be interesting.  

(c) The proposed algorithm achieves a near-optimal regret, low communication complexity and switching cost simultaneously.

Weaknesses

(a) The proposed algorithm shows that at each time $t$, only one client exchanges parameters to the server. It seems that this setting is not reasonable and could make the collaboration less effective. 

(b) In Algorithm 1, the parameters exchanged between the server and the client are $\Sigma$ and $u$, which may lead to the privacy leakage of local data. 

(c) The motivation of this work is not very clear. The authors should pay more attention to this issue. 

(d) There lack of numerical experiments to support the theoretical findings.
questions: (a) The proposed algorithm shows that at each time $t$, only one client exchanges parameters to the server. Is this setting reasonable? Does this make the collaboration less effective? Are there any practical applications fit for this setting?

(b) How about the performance of the proposed algorithm in dealing with some real-world applications?

limitations: (a) In Algorithm 1, the parameters exchanged between the server and the client are $\Sigma$ and $u$, which may lead to the privacy leakage of local data. I suggest the authors refer to the work [Dubey and Pentland, 2020] to address this issue. 

(b) It would be better to conduct some numerical experiments to support the merits of the proposed algorithm.
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: The paper considers asynchronous federated contextual linear bandits problem, where each agent faces a single contextual linear bandits model and the parameters are the same. The learning objective is to minimize the cumulative regret of all agents. By a novel analysis, the paper prove that a simple algorithm called FedLinUCB enjoys regret upper bound $O(d\sqrt{MT})$, where d is the dimension of parameter space, M is the number of agents, and T is the time horizon. The paper also gives an lower bound of the communication cost scales $\Omega(dM)$.
strengths_and_weaknesses: The primary novelty of the paper is to provide an analysis for fully asynchronous federated linear contextual bandits, where each agent can independently decide whether it communicates with the central server. The paper is well-written and sound.

While the independency between agents' communication is new, the algorithm also restricts the inactive agents to download new information from the server.

questions: As mentioned above, IMHO, there may be some benefits if inactive agents are allowed to download new information. Is it possible to close the gap of communication cost upper and lower bound by personalized event-trigger downloading procedure?


------------
Thank the author for the explanation. My concerns are addressed and I decide to keep my score.
limitations: Yes
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 proposes the FedLinUCB algorithm for asynchronous federated contextual linear bandits. The authors prove that the algorithm has a tight regret upper bound and low communication complexity.
strengths_and_weaknesses: 1. Strengths
	1. Propose a better communication protocol that fits the asynchronous setting;
	2. Provide a new method to derive LinUCB's upper bound in the asynchronous setting.
	3. The author did a very good job in presenting their work. 
2. Weaknesses:
	1. My major concern lies in the significance. The strengths above are not major compared to [Li and Wang 2022, AISTATS]. Because FedLinUCB is a (very) minor modification of [Li and Wang 2022] in communication protocol: given the same communication condition (determinant-based criterion), the difference is only in *how* agent and server communicate. (also see the paper's Table 1's last two rows).
	2. Secondly, in my opinion, the originality also does not reach the NeurIPS bar. The model is not new. The algorithmic technique is already broadly used (already in the same model as well). Only the analysis technique is novel, though seems minor (since it only works in this specific federated contextual linear bandits' LinUCB algorithm). 

------
After rebuttal: I thank the author for the detail comparison [Li and Wang, 2022] and the additional experiments. My concerns are addressed. I raised my score to weak accept. 
questions: Why don't you provide simulation results? If my guess is right, in numerical simulation, FedLinUCB would have almost the same performance as [Li and Wang 2022], if not a little worse. But FedLinUCB could still have a smaller communication time.
limitations: This part of the paper looks good for me.
review_title: null

Meta-review: metareview: The reviewers all recommend acceptance (with various extent), and the AC also shares their opinion.

Regarding the experiments, please make sure that the final version of the paper complies with the relevant parts of the checklist (e.g., report error bars). It could also be interesting to see an experiment where $\theta^*$ is non-uniform.
confidence: Certain
Decision: Accept