Adaptation minimax pour les bandits à continuum de bras

Mercredi 29 mai 10:30-11:30 - Hédi Hadiji

Résumé : Lundi matin, alors que vous rentrez dans votre casino, vous constatez que l’on a remplacé le bandit manchot (votre machine à sous fétiche), par un bandit à K bras. Chaque bras renvoie un paiement identiquement distribué, selon une distribution inconnue et propre à ce bras. Quelle stratégie adopter pour maximiser vos gains ? Mardi matin, ce ne sont plus K bras auxquels vous faites face, mais un continuum de bras indexés par [0, 1]. Il y a trop d’actions, il n’est plus possible de faire quoi que ce soit d’intelligent ! Le patron, qui vous aime bien, vous explique alors que la fonction de paiement moyen est Hölder régulière, d’exposant $\alpha$. Pourrez-vous recycler votre stratégie élaborée la veille pour le bandit à K bras ? Mercredi matin, après avoir débriefé vos aventures des deux jours précédents, nous nous intéresserons au cas où vous savez que la fonction est Hölder régulière, mais sans connaître la vraie valeur de l’exposant.
Minimax adaptation for continuum-armed bandits
In the multi-armed bandit problem, a player must sequentially choose between a finite set of actions, or arms, trying to maximize her reward in the process. When the number of arms is large, some assumptions have to be made if we wish to obtain meaningful guarantees on the performance of our algorithms. Such assumptions typically come as a Hölder condition on the mean-payoff function The first algorithms designed for this problem needed the true value of the smoothness, that is, the Hölder exponent, to perform optimally. This is often unrealistic, and one naturally wonders how to do without this knowledge. In this talk, I’ll introduce the usual (stochastic) multi-armed bandit problem, and some near-minimax optimal strategies in the finite-armed setting. We will see how t generalize these strategies to the case of continuum-armed bandits, first in the known smoothness case, and then in the unknown smoothness case.

Lieu : Salle 3L15

Adaptation minimax pour les bandits à continuum de bras  Version PDF