Bandits for Exploration: Best Arm Identification and Discovery with Probabilistic Experts

Whereas the achievable limits in terms of regret minimization in simple bandit models are now well known, it is often meaningful to consider slightly different goals and/or slightly different models.
In this talk, I first present recent contributions to a better understanding of the complexity of identifying the m-best arms. Generic notions of complexity are introduced and investigated for the two dominant frameworks considered in the literature: fixed-budget and fixed-confidence settings.
Then, I present optimal discovery with probabilistic expert advice, a problem arising from security analysis of power systems. While not involving a bandit model, I will show how some basic ideas of the bandit literature still lead to optimal solutions.