Politiques d'index basées sur la moyenne d'échantillon avec regret O(logn) pour le problème du bandit manchot

Nous considérons une version non-bayésienne à horizon infini du problème du bandit manchot avec l'objectif de concevoir des politiques simples dont le regret augmente lentement avec le temps. Dans leur travail fondamental sur ce problème, Lai et Robbins avaient obtenu une borne inférieure O (log n ) sur le regret avec une constante qui dépend du nombre de Kullback–Leibler. Ils ont également construit des politiques pour certaines familles spécifiques de distributions de probabilité (y compris les familles exponentielles) qui atteignaient la borne inférieure. Dans cet article, nous construisons des politiques d'index qui dépendent des récompenses de chaque bras uniquement par le biais de leur moyenne d'échantillon. Ces politiques sont beaucoup plus simples à calculer et sont également applicables de manière beaucoup plus générale. Elles atteignent un regret O (log n) avec une constante qui est également basée sur le nombre de Kullback–Leibler. Cette constante s'avère optimale pour les familles exponentielles à un paramètre ; cependant, en général, elle est dérivée de l'optimal via un principe de 'contration'. Nos résultats s'appuient entièrement sur quelques lemmes clés de la théorie des grandes déviations.