Federated High-Dimensional Online Decision Making

Abstract

We resolve the main challenge of federated bandit policy design via exploration-exploitation trade-off delineation under data decentralization with a local privacy protection argument. Such a challenge is practical in domain-specific applications and admits another layer of complexity in applications of medical decision-making and web marketing, where high- dimensional decision contexts are sensitive but important to inform decision-making. Exist- ing (low dimensional) federated bandits suffer super-linear theoretical regret upper bound in high-dimensional scenarios and are at risk of client information leakage due to their in- ability to separate exploration from exploitation. This paper proposes a class of bandit policy design, termed Fedego Lasso, to complete the task of federated high-dimensional online decision-making with sub-linear theoretical regret and local client privacy argument. Fedego Lasso relies on a novel multi-client teamwork-selfish bandit policy design to per- form decentralized collaborative exploration and federated egocentric exploration with log- arithmic communication costs. Experiments demonstrate the effectiveness of the proposed algorithms on both synthetic and real-world datasets.