TL;DR
This paper introduces SAMBA, a novel framework for secure federated multi-armed bandits. SAMBA allows multiple data owners to collaboratively train bandit algorithms without revealing their private data, achieving the same cumulative reward as non-secure versions while providing formal security guarantees. This is crucial for applications like recommendation systems where data privacy is paramount.
What Problem Does This Paper Address?
The paper tackles the challenge of performing multi-armed bandit (MAB) learning in a federated setting while ensuring data privacy. In MAB problems, an agent sequentially chooses actions (arms) to maximize cumulative rewards from unknown reward distributions. Federated learning (FL) allows multiple data owners to collaborate on a learning task without sharing their raw data, coordinated by a central server. However, applying MAB in FL raises significant privacy concerns: data owners' local data (which defines the reward distributions for their arms) must remain private, and the central server should not learn sensitive information like which arm is pulled or the rewards obtained. Existing federated learning approaches often focus on model aggregation, not on the sequential decision-making inherent in MAB. Furthermore, directly applying cryptographic techniques like fully homomorphic encryption (FHE) to MAB is computationally prohibitive due to the complexity of operations like comparisons. This paper aims to bridge this gap by proposing a secure and generic FL framework for MAB.
Methods
SAMBA is a generic framework designed to securely instantiate various MAB algorithms. Its core innovation lies in distributing server-side computations between two nodes: a Controller and a Comp node.
- Controller: Interacts with data customers (DC) and data owners (DOs). It receives encrypted scores from DOs and forwards them to Comp. Crucially, it does not have access to the decryption keys for these scores.
- Comp: Receives encrypted scores from the Controller. It can decrypt and compare these scores. To prevent the Controller from associating scores with specific DOs, Comp receives scores that have been permuted and masked.
The framework uses a combination of cryptographic primitives:
- AES-GCM: For symmetric encryption, used to encrypt messages between DOs and the Controller, and between the Controller and Comp. This ensures that an external observer cannot read the exchanged data.
- Paillier Encryption: For asymmetric encryption, used to encrypt the final cumulative reward. This additive homomorphic property allows the summation of encrypted rewards from all DOs, and only the data customer (DC) with the private key can decrypt the final sum.
The framework also employs:
- Random Masks ($\alpha_t$): Applied by DOs to their arm scores before encryption. These masks are order- and proportion-preserving, allowing for correct computation of argmax and probability matching without revealing the original scores.
- Random Permutations ($\sigma_t$): Applied by the Controller before sending encrypted scores to Comp. This further obfuscates the association between scores and DOs.
SAMBA is designed to be generic, allowing the instantiation of any MAB algorithm that satisfies two properties: (1) Arm score locality: the score computation for an arm depends only on the DO's local variables. (2) Oblivious arm selection: Comp can select an arm based on permuted and masked scores without learning the actual scores or their original owners.
Datasets
The paper uses two publicly available datasets for evaluation:
- MovieLens: A dataset of user ratings for movies.
- Jester: A dataset of user ratings for jokes.
These datasets are preprocessed to extract item (movie/joke) ratings, which serve as rewards for the bandit arms. The authors note that this experimental setup is typical for stochastic MAB research.
Key Insights and Ideas
- Decoupling Server Roles: Splitting server computations between a Controller and a Comp node is key to achieving security. The Controller orchestrates but doesn't see sensitive data, while Comp performs comparisons but receives obfuscated inputs.
- Order and Proportion Preservation: The use of specific types of masks (order- and proportion-preserving) is crucial. It allows the core logic of MAB algorithms (like finding the maximum score or performing probability matching) to function correctly even on masked and encrypted data.
- Genericity through Abstraction: By abstracting score computation and arm selection into
ComputeScoreandSelectArmfunctions, SAMBA can accommodate a wide range of MAB algorithms, provided they meet specific locality and obliviousness criteria. - Security without Performance Degradation: The framework guarantees that the secure federated version of an algorithm returns the exact same cumulative reward as its non-secure, non-federated counterpart. This is a significant advantage over differential privacy approaches, which often introduce a performance trade-off.
Key Results
- Correctness: Theoretical analysis and experimental results confirm that SAMBA instantiations of MAB algorithms yield the same cumulative reward as their standard counterparts.
- Security: Formal proofs demonstrate that SAMBA satisfies strong security properties under the honest-but-curious threat model, preventing data leakage to unauthorized participants (DOs, Server, External Observers) and ensuring only the DC sees the final cumulative reward.
- Scalability: Experimental results show that SAMBA's execution time scales linearly with the budget ($N$) and the number of arms ($K$), matching theoretical predictions.
- Overhead: The cryptographic overhead is manageable, with AES-GCM operations dominating Paillier operations. For maximal inputs ($N=10^5, K=100$), execution times are around 15 minutes, which is considered reasonable for a data customer. Pursuit, requiring two iterations per time step, takes about double the time.
Limitations and Future Work
- Algorithm Instantiation: While SAMBA is generic, some algorithms (like Reinforcement Comparison) cannot be instantiated due to their reliance on global information for score computation. Hypothetical algorithms that violate oblivious arm selection are also non-instantiable.
- Reward Models: The current framework is designed for Bernoulli reward distributions. Extending SAMBA to other bandit models, such as linear bandits, is identified as a significant future research direction. This would require adapting the genericity properties and potentially developing new secure protocols.
- Threat Models: The current security guarantees are based on the honest-but-curious threat model. Future work could explore more complex threat models, such as Byzantine adversaries.
- Practical Optimizations: While the theoretical complexity is $O(NK)$, algorithm-specific optimizations (e.g., for the exploration phase of $\epsilon$-greedy) can reduce practical complexity, though not the asymptotic bound. The authors implemented some of these in their prototype.
Summary updated