Test séquentiel pour la moyenne la plus basse : De l'échantillonnage de Thompson à celui de Murphy.

Résumé L'apprentissage de la moyenne minimale/maximale parmi un ensemble fini de distributions est une sous-tâche fondamentale en planification, en recherche d'arbres de jeux et en apprentissage par renforcement. Nous formalisons cette tâche d'apprentissage comme le problème de tester séquentiellement comment la moyenne minimale parmi un ensemble fini de distributions se compare à un seuil donné. Nous développons des limites inférieures non asymptotiques raffinées, qui montrent que l'optimalité exige un comportement d'échantillonnage très différent pour un vrai minimum faible ou élevé. Nous montrons que l'échantillonnage de Thompson et la politique intuitive des limites inférieures de confiance ne règlent chacun qu'un seul de ces cas. Nous développons une nouvelle approche que nous appelons l'échantillonnage de Murphy. Bien qu'elle ne prenne en compte que les vrais minima faibles, nous prouvons qu'elle est optimale pour les deux possibilités. Nous concevons ensuite des inégalités de déviation auto-normalisées avancées, alimentant des règles d'arrêt plus agressives. Nous complétons nos garanties théoriques par des expériences montrant que le MS fonctionne le mieux en pratique.