Open AccessSAMBA: A Generic Framework for Secure Federated Multi-Armed Bandits
Author(s) -
Radu Ciucanu,
Pascal Lafourcade,
Gael Marcadet,
Marta Soare
Publication year - 2022
Publication title -
journal of artificial intelligence research/the journal of artificial intelligence research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.79
H-Index - 123
eISSN - 1943-5037
pISSN - 1076-9757
DOI - 10.1613/jair.1.13163
Subject(s) - computer science , orchestration , overhead (engineering) , reinforcement learning , multi armed bandit , cryptography , maximization , hash function , distributed computing , range (aeronautics) , outcome (game theory) , artificial intelligence , theoretical computer science , computer security , machine learning , mathematical optimization , operating system , regret , art , musical , materials science , mathematics , mathematical economics , composite material , visual arts
The multi-armed bandit is a reinforcement learning model where a learning agent repeatedly chooses an action (pull a bandit arm) and the environment responds with a stochastic outcome (reward) coming from an unknown distribution associated with the chosen arm. Bandits have a wide-range of application such as Web recommendation systems. We address the cumulative reward maximization problem in a secure federated learning setting, where multiple data owners keep their data stored locally and collaborate under the coordination of a central orchestration server. We rely on cryptographic schemes and propose Samba, a generic framework for Secure federAted Multi-armed BAndits. Each data owner has data associated to a bandit arm and the bandit algorithm has to sequentially select which data owner is solicited at each time step. We instantiate Samba for five bandit algorithms. We show that Samba returns the same cumulative reward as the nonsecure versions of bandit algorithms, while satisfying formally proven security properties. We also show that the overhead due to cryptographic primitives is linear in the size of the input, which is confirmed by our proof-of-concept implementation.