Federated Linear Bandits with Finite Adversarial Actions
Li Fan Ruida Zhou Chao Tian Cong Shen
We study 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 that may be different across clients. To address the
unique challenges of adversarial finite action sets, we propose the
FedSupLinUCB algorithm, which extends the principles of SupLinUCB and OFUL
algorithms in linear contextual bandits. We prove that FedSupLinUCB achieves a
total regret of $\tilde{O}(\sqrt{d T})$, where $T$ is the total number of arm
pulls from all clients, and $d$ is the ambient dimension of the linear model.
This matches the minimax lower bound and thus is order-optimal (up to polylog
terms). We study both asynchronous and synchronous cases and show that the
communication cost can be controlled as $O(d M^2 \log(d)\log(T))$ and
$O(\sqrt{d^3 M^3} \log(d))$, respectively. The FedSupLinUCB design is further
extended to two scenarios: (1) variance-adaptive, where a total regret of
$\tilde{O} (\sqrt{d \sum \nolimits_{t=1}^{T} \sigma_t^2})$ can be achieved with
$\sigma_t^2$ being the noise variance of round $t$; and (2) adversarial
corruption, where a total regret of $\tilde{O}(\sqrt{dT} + d C_p)$ can be
achieved with $C_p$ being the total corruption budget. Experiment results
corroborate the theoretical analysis and demonstrate the effectiveness of
FedSupLinUCB on both synthetic and real-world datasets.