Best Arm Identification in Multi-Agent Multi-Armed Bandits
Jul 24, 2023
Speakers
Filippo Vannella
Speaker · 0 followers
Alexandre Proutiere
Speaker · 0 followers
Jaeseong Jeong
Speaker · 0 followers
About
We investigate the problem of best arm identification in Multi-Agent Multi-Armed Bandits (MAMABs) where the rewards are defined through a factor graph. The objective is to find an optimal global action with a prescribed level of confidence and minimal sample complexity. We derive a tight instance-specific lower bound of the sample complexity and characterize the corresponding optimal sampling strategy. Unfortunately, this bound is obtained by solving a combinatorial optimization problem with a number of variables and constraints exponentially growing with the number of agents. We leverage Mean Field (MF) techniques to obtain, in a computationally efficient manner, a tight approximation of the lower bound. The approximation scales at most as ρ K^d (where ρ, K, and d denote the number of factors in the graph, the number of possible actions per agent, and the maximal degree of the factor graph). We devise MF-TaS (Mean-Field-Track-and-Stop), an algorithm whose sample complexity provably matches our approximated lower bound. We illustrate the performance of MF-TaS numerically using both synthetic and real-world experiments (e.g., to solve the antenna tilt optimization problem in radio communication networks).We investigate the problem of best arm identification in Multi-Agent Multi-Armed Bandits (MAMABs) where the rewards are defined through a factor graph. The objective is to find an optimal global action with a prescribed level of confidence and minimal sample complexity. We derive a tight instance-specific lower bound of the sample complexity and characterize the corresponding optimal sampling strategy. Unfortunately, this bound is obtained by solving a combinatorial optimization problem with a n…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Learning-Rate-Free Learning by D-Adaptation
Watch later
PLay: Parametrically Conditioned Layout Generation Using Latent Diffusion
Watch later
Challenges with alignment in practice
Watch later
Esin Durmus, …
Evolving Semantic Prototype Improves Generative Zero-Shot Learning
Watch later
Shiming Chen, …
Designing High-Dimensional Closed-Loop Optimal Control Using Deep Neural Networks
Watch later
Jiequn Han, …
