Federated Linear Bandits with Finite Adversarial Actions

Summary

This paper studies the linear contextual bandits problem with federated learning of $M$ clients communicating with a central sever. In particular, the paper assumes adversarial finite action, and considers two cases of the communication: asynchronous and synchronous. Following the idea of OFUL, this work extends the previous SupLinUCB in linear contextual bandits to deal with the federated learning scenario, and proposes the algoirthm FedSupLinUCB which achieves $\widetilde{O}(\sqrt{dT})$ where $T$ is the total number of pulls (the summation of cumulative pulls over $M$ clients together), and $d$ is the dimension. More importantly, this result is attained with limited communication cost $\mathcal{O}(\sqrt{d^3M^3}\log(d))$ for synchronous case, and $\mathcal{O}(dM^2\log(d)\log(T))$ for asynchronous case. In addition, the FedSupLinUCB further extends to the variance-adaptive and adversarial corruption scenarios.

Strengths

The paper is clearly-written and well-organized. The notations are well-defined and the meanings are explained clearly prior to their usages. 1. Combining online learning and federated learning is an interesting direction. The proposed algorithm attains the optimal regret bound of such problem up to some $\log T$ factors, and further ensures limited communication cost, which could be dominating in the distributed systems. Among these results, the most interesting one is that for the synchronous case, which is independent with the horizon $T$. 2. The instance-dependent regret bounds for the variance-adaptive and adversarial corruption scenarios are also very interesting. The worst case regret bound is not meaningful in most real world applications.

Weaknesses

This paper does not have any specific weakness.

Questions

1. Any lower bound of the communication cost in the synchronous case or the asynchronous case? 2. Any idea to improve the regret bounds to the optimal regret bound $\mathcal{O}(\sqrt{dT\log T})$, which can be obtained by Fed-PE?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

This work is pure theoretical, and does not have any negative societal impact.

Summary

This paper studies a federated linear bandits model, where M clients communicate with a central server to solve a linear contextual bandits problem with finite adversarial action sets and proposes the FedSupLinUCB algorithm, which extends the SupLinUCB and OFUL principles in linear contextual bandits. Both asynchronous and synchronous cases are considered. Experiment results corroborate the theoretical analysis and demonstrate the effectiveness of FedSupLinUCB on both synthetic and real-world datasets.

Strengths

The method description, theoretical derivation and complexity analysis of the article are very detailed and well organized.

Weaknesses

See Questions part.

Questions

1. Do the adversarial corruption actios only exist in the setting of asynchronous case? 2. Are there differences in intensity for adversarial actions? If so, do different intensities have different effects on the experimental scene? 3. Is Robust Async-FedSupLinUCB a general robust method or can only be used against a specific adversarial setting？

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

In this work, the authors consider the problem of Federated linear bandits with finite adversarial actions. This is the first time investigating a setting where federated clients are faced with a set of actions to choose from that changes over time in an oblivious adversarial manner, and the authors of this paper do so for both synchronous and asynchronous versions of the problem. To handle this problem, the authors propose two algorithms that are based on SupLinUCB (Chen et al. 2011), which is a standard approach for linear bandits and adapted to federated bandits. Then, they combine this S-LUCB approach with two different protocols to tackle both the asynchronous and the synchronous version of the problem.One of the challenges of federated learning comes with the cost of the communication between the clients and the server. In the asynchronous setting, only one client is active at the time and the the synchronization rate depends on each individual client. For this problem, the authors prove that the proposed algorithm achieves an order optimal (up to log factors) high probability bound of order $O(\sqrt{dT})$ while ensuring that their total communication cost is logarithmic in T. In the synchronous case, layers of clients work simultaneously which allows for the server to take advantage of the various information provided by the clients. This means that these clients don't just synchronize when the information that they have has changed, but they also do so periodically to ensure that their information is up to date. This extra information provided by the server to the clients allows to actually lower the total number of communications and obtain a $\tilde O(\sqrt{dMT_c})$ regret bound while keeping a time independent bound on the number of communication. The authors provide detailed proofs of their results in the appendices and experiments, both on generated and real life datasets to highlight how the regret and the communication costs evolve in terms of arrival patterns and number of clients.

Strengths

This works studies a new variant of the federated linear bandits problem where the clients are facing finite adversarial arm sets instead of either finite fixed armed sets or infinite arm sets. To do so, they build upon existing algorithms for linear bandits with an adversarial arm set, SupLinUCB (Chu et al. 2011) and for asyncronous federated learning FedLinUCB (He et al. 2022a). The novelty of their approach mainly resides in the improved communication protocol, in particular in the synchronous setting, where they take advantage of a layer structure to limit the communication cost while still synchronizing regularly. In both the asynchronous and the synchronous settings, they recover the regret of SupLinUCB in the single player setting (Chu et al. 2011), and are within a log T factor of the state of the art results for federated synchronous and asynchronous learning, both in terms of regret and communication costs. Overall, this is a well presented paper that provides some interesting results for a new variation of the federated learning problem, which might be more relevant in practice, which is reinforced by the fact that they also run experiments on real worlds datasets. Presenting results for the corrupted setting is also a nice generalization of their results.

Weaknesses

In the experiments section, it would be interesting to see the proposed algorithms compared with other results for federated learning: The results in Appendix H are promising and could benefit from being extended. It would also be nice if the legends on the plot could be larger so it is a bit easier to read.

Questions

The problems studied in federated learning are very close to these of multiplayer multiarmed bandits. Have you thought of whether there are results that could bridge the two settings?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

NA

Summary

This paper addresses the linear bandits problem in the context of federated learning. It proposes a general algorithm called FedSupLinUCB that solves a linear contextual bandit problem with finite adversarial action sets that may vary across clients. The paper also considers practical challenges in federated settings such as synchrony, communication efficiency, and time-evolving scenarios.

Strengths

This paper explores the linear contextual bandit problem with finite adversarial action sets in the federated learning setting. Additionally, it addresses several practical challenges in federated settings, such as synchrony, communication efficiency, and time-evolving scenarios.

Weaknesses

Background and challenge: - The introduction and preliminaries do not provide a detailed definition of the time-evolving and adversarial arm. To improve comprehension, it would be helpful to explain the impact of these factors on the federated linear bandit problem. - Although the paper discusses the main challenges of federated linear bandits, it should emphasize the key differences from traditional linear bandit problems, such as single-player bandits or distributed bandits. - The paper lacks strong motivation due to the vague background and challenge. Novelty: - The main theoretical contributions of the paper extend previous work on linear bandit problems to the federated setting. For example, FedSumLinUCB is an extension of SupLinUCB and OFUL. Robust Async-FedSupLinUCB incorporates ideas from He et al. (2020b). - The theory and methodology employed in the paper appear to be borrowed from the literature. Experiment setting: - The reward function utilized in the experiments, where $r_{t, a}=\theta^{\top} x_{t, a}+\epsilon_t$ , does not align with the settings described in the paper. To my knowledge, it is more general to let the reward function different across clients with certain variances according to the environments. - The experiments conducted in the paper are limited. Only a classic algorithm proposed in 2011 by Chu et al. is used as a baseline, and not all proposed algorithms are fully evaluated. Writing: - It is unusual for a conference paper to have 10 sections.

Questions

- What are the specific challenges in the federated linear bandit problem? Federated learning was originally proposed to address data-sharing issues. Does the federated linear bandit problem face similar challenges related to system efficiency and heterogeneity? - What unique solutions or methods does the paper contribute? It appears that some challenges have already been addressed by previous works.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

No limitations are discussed in the main paper.

Response to author's rebuttal

Thanks to the authors' response which has addressed my minor concerns, and I will keep my preliminary rating

Please engage in the rebuttal

Dear reviewer, Please at least acknowledge the author's response and ideally explain if and why their reply does not change your mind.

Please engage in the rebuttal

Dear reviewer, Please acknowledge the author's response and tell us if the replies changed your assessment.

Discussion overview

Dear reviewers and authors, From the rebuttal, I take away that there are no strong disagreements between authors and reviewers on any factual matters in the paper. The main reason the scores are not higher, is that the reviewers are not convinced of the significance and novelty of the proposed algorithmic solution, correct?

Thanks for the feedback

Thank you for addressing my concerns. However, I remain uncertain, especially in terms of the core challenges in FL like client data heterogeneity, the distinct difference between distributed bandit and federated bandit, and the paper's singular contributions beyond the amalgamation of techniques from two distinct domains.