Les algorithmes de bandit de types N-S ont été introduits dans les années 60 en vue d'applications aux tests cliniques notamment. Le principe d'un algorithme de bandit peut être défini de la manière suivante : on dispose de 2 sources A et B (ayant respectivement une probabilité pA et pB d'être satisfaisante lorsque qu'elle est utilisée) et on souhaite déterminer laquelle des deux est la plus performante. Récemment Lamberton et Pagès ont introduit une version dite “pénalisée” de cet algorithme pour laquelle divers résultats de convergence ont été démontrés. Nous nous intéressons dans ce travail à la question suivante : ces algorithmes sont-ils performants d'un point de vue de regret ? Le regret étant la différence entre la meilleure performance possible (i.e celle obtenue en choisissant toujours la meilleur source) et celle obtenue par l'algorithme. Dans cette présentation, nous verrons qu'une légère modification de cette algorithme conduit à des bornes de regret de l'ordre de \sqrt{n} uniformément en pA et pB. Nous étendrons aussi les résultats de Lamberton et Pagès à une version multidimensionnelle de l'algorithme. Nous établirons une convergence en loi vers la mesure invariante d'un PDMP pour lequel nous étudierons sa convergence à l'équilibre. Travail effectué en collaboration avec Sébastien Gadat et Fabien Panloup.