On répète la situation suivante : à chaque tour, le statisticien doit choisir une parmi K lois de probabilité sur
[0,1] (inconnues) et reçoit un paiement tiré selon cette loi. Son objectif est de maximiser la somme de ses paiements : il est donc tiraillé entre deux objectifs, mieux connaître ces K probabilités (et donc, les choisir toutes suffisamment souvent pour bien les estimer) et exploiter ces connaissances (en choisissant surtout les probabilités chargeant les plus grandes valeurs). Nous introduirons le regret comme mesure de la performance d'une stratégie de choix, et nous étudierons plus particulièrement les bornes inférieures de performance sur le regret, qui sont en termes de divergences de Kullback-Leibler.
Le résultat majeur sera une preuve courte et claire de la borne inférieure optimale de Lai et Robbins (1985) et Burnetas et Katehakis (1996).