Incentivized Truthful Communication for Federated Bandits
Zhepei Wei Chuanhao Li Tianze Ren Haifeng Xu Hongning Wang
To enhance the efficiency and practicality of federated bandit learning,
recent advances have introduced incentives to motivate communication among
clients, where a client participates only when the incentive offered by the
server outweighs its participation cost. However, existing incentive mechanisms
naively assume the clients are truthful: they all report their true cost and
thus the higher cost one participating client claims, the more the server has
to pay. Therefore, such mechanisms are vulnerable to strategic clients aiming
to optimize their own utility by misreporting. To address this issue, we
propose an incentive compatible (i.e., truthful) communication protocol, named
Truth-FedBan, where the incentive for each participant is independent of its
self-reported cost, and reporting the true cost is the only way to achieve the
best utility. More importantly, Truth-FedBan still guarantees the sub-linear
regret and communication cost without any overheads. In other words, the core
conceptual contribution of this paper is, for the first time, demonstrating the
possibility of simultaneously achieving incentive compatibility and nearly
optimal regret in federated bandit learning. Extensive numerical studies
further validate the effectiveness of our proposed solution.