Secure Best Arm Identification in Multi-Armed Bandits
| Autor: | Pascal Lafourcade, Marius Lombard-Platet, Marta Soare, Radu Ciucanu |
|---|---|
| Přispěvatelé: | Sécurité des Données et des Systèmes (SDS), Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS), Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Be-Studys, Université d'Orléans (UO), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université d'Orléans (UO), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), École normale supérieure - Paris (ENS Paris), Département d'informatique de l'École normale supérieure (DI-ENS) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Mathematical optimization
Computer science Cloud computing 02 engineering and technology 010501 environmental sciences 01 natural sciences Outcome (game theory) Paillier cryptosystem Outsourcing [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] Multi-Armed Bandits [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG] 0202 electrical engineering electronic engineering information engineering Distributed Computation 0105 earth and related environmental sciences Best Arm Identification business.industry 16. Peace & justice Parameter identification problem Identification (information) Action (philosophy) Paillier Cryptosystem Privacy 020201 artificial intelligence & image processing business Decision-making models |
| Zdroj: | ISPEC 2019 : The 15th International Conference on Information Security Practice and Experience ISPEC 2019 : The 15th International Conference on Information Security Practice and Experience, Nov 2019, Kuala Lumpur, Malaysia. ⟨10.1007/978-3-030-34339-2_9⟩ Information Security Practice and Experience ISBN: 9783030343385 ISPEC |
| DOI: | 10.1007/978-3-030-34339-2_9⟩ |
| Popis: | International audience; The stochastic multi-armed bandit is a classical decision making model, where an 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 action. A popular objective for the agent is that of identifying the arm with the maximum expected reward, also known as the best-arm identification problem. We address the inherent privacy concerns that occur in a best-arm identification problem when outsourcing the data and computations to a honest-but-curious cloud.Our main contribution is a distributed protocol that computes the best arm while guaranteeing that (i) no cloud node can learn at the same time information about the rewards and about the arms ranking, and (ii) by analyzing the messages communicated between the different cloud nodes, no information can be learned about the rewards or about the ranking. In other words, the two properties ensure that the protocol has no security single point of failure. We rely on the partially homomorphic property of the well-known Paillier's cryptosystem as a building block in our protocol. We prove the correctness of our protocol and we present proof-of-concept experiments suggesting its practical feasibility. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|