Network of Bandits insure Privacy of end-users
This work addresses privacy concerns for end-users in distributed systems by preventing event storage, though it is incremental as it builds on existing bandit algorithms.
The paper tackles the problem of distributed best arm identification in a network of bandits to preserve user privacy by processing data at the edge, resulting in an algorithm that is optimal in transmitted bits and near-optimal in speed-up factor compared to independent runs.
In order to distribute the best arm identification task as close as possible to the user's devices, on the edge of the Radio Access Network, we propose a new problem setting, where distributed players collaborate to find the best arm. This architecture guarantees privacy to end-users since no events are stored. The only thing that can be observed by an adversary through the core network is aggregated information across users. We provide a first algorithm, Distributed Median Elimination, which is optimal in term of number of transmitted bits and near optimal in term of speed-up factor with respect to an optimal algorithm run independently on each player. In practice, this first algorithm cannot handle the trade-off between the communication cost and the speed-up factor, and requires some knowledge about the distribution of players. Extended Distributed Median Elimination overcomes these limitations, by playing in parallel different instances of Distributed Median Elimination and selecting the best one. Experiments illustrate and complete the analysis. According to the analysis, in comparison to Median Elimination performed on each player, the proposed algorithm shows significant practical improvements.