Budget-Constrained Federated Bandits for Mobile Applications

摘要

With the development of federated learning and mobile computing, federated bandit frameworks have been proposed to enable multiple clients to explore and exploit collaboratively under the guarantee of data privacy. However, none of them take the widespread budget constraints into account. In this work, we introduce the Federated linear Bandits framework with Knapsacks (FBwK), where M clients can pull K arms with linear rewards and costs to minimize the total regret under the coordination of a central server. For FBwK, we propose a new definition of OPT solution and a bandit algorithm, namely FedUCBwK. Specifically, we design a uniform policy parameter update threshold for each client, which balances regret, communication, and computation costs. In this process, the central server uses a factor on knapsack constraints to pace the budget consumption and preserve the clients’ privacy by transmitting model updates instead of raw data. We conduct a theoretical analysis and show that FedUCBwK achieves a sublinear regret with logarithmic communication and computation. Evaluation on real-world mobile application datasets demonstrates that FedUCBwK consistently outperforms existing methods across diverse tasks.