Exploration pure dans les modèles de bandits à bras infinis avec confiance fixe.

Résumé Nous considérons le problème de l'identification quasi-optimale des bras dans le cadre de confiance fixe du problème du bandit infiniment armé lorsque rien n'est connu de la distribution du réservoir des bras. Nous (1) introduisons un cadre de type PAC dans lequel nous pouvons dériver et présenter des résultats. (2) dériver une limite inférieure de complexité d'échantillon pour une identification de bras quasi-optimale. (3) proposer un algorithme qui identifie un bras quasi-optimal avec une probabilité élevée et dériver une limite supérieure sur sa complexité d'échantillon qui est dans un facteur logarithmique de notre limite inférieure. et (4) discuter si notre dépendance log^2(1/delta) est inéluctable pour les algorithmes "à deux phases" (sélectionner les bras d'abord, identifier le meilleur plus tard) dans le cadre infini. Ce travail permet d'appliquer les modèles de bandit à une classe plus large de problèmes pour lesquels moins d'hypothèses s'appliquent.