Decentralized Exploration in Multi-Armed Bandits

By Raphaël Féraud, Réda Alami, Romain Laroche. 2018

26 citations recorded by the source corpus.

We consider the decentralized exploration problem: a set of players collaborate to identify the best arm by asynchronously interacting with the same stochastic environment. The objective is to insure privacy in the best arm identification problem between asynchronous, collaborative, and thrifty players. In the context of a digital service, we advocate that this decentralized approach allows a good balance between the interests of users and those of service providers: the providers optimize their services, while protecting the privacy of the users and saving resources. We define the privacy level as the amount of information an adversary could infer by intercepting the messages concerning a single user. We provide a generic algorithm Decentralized Elimination, which uses any best arm identification algorithm as a subroutine. We prove that this algorithm insures privacy, with a low communication cost, and that in comparison to the lower bound of the best arm identification problem, its sample complexity suffers from a penalty depending on the inverse of the probability of the most frequent players. Then, thanks to the genericity of the approach, we extend the proposed algorithm to the non-stationary bandits. Finally, experiments illustrate and complete the analysis.

Subfields: Artificial Intelligence, Computer Science Applications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Rémi Tachet des Combes
2. Thiago D. Simão
3. Romain Laroche

In Computer Science Applications

1. Rémi Tachet des Combes
2. Thiago D. Simão
3. Romain Laroche

In Management Science and Operations Research

1. Rémi Tachet des Combes
2. Thiago D. Simão
3. Romain Laroche

Citations in the corpus

• Safe Policy Improvement with an Estimated Baseline Policy (2019, methodology): “These RWTs entail a high parallellization of the trajectory collection and strict communication constraints both in bandwidth and in privacy [4].”