Sur l'optimalité de l'algorithme de Hedge dans le régime stochastique.

Résumé Dans cet article, nous étudions le comportement de l'algorithme Hedge dans le cadre stochastique en ligne. Nous prouvons que l'algorithme Hedge à tout moment avec un taux d'apprentissage décroissant, qui est l'un des algorithmes les plus simples pour le problème de la prédiction avec avis d'experts, est remarquablement à la fois optimal dans le pire des cas et adaptatif aux problèmes stochastiques et adversatifs avec un écart plus faciles. Cela montre que, malgré son petit taux d'apprentissage non adaptatif, Hedge possède la même garantie de regret optimal dans le cas stochastique que les algorithmes adaptatifs récemment introduits. De plus, notre analyse montre des différences qualitatives avec d'autres versions de l'algorithme de Hedge, telles que la variante à horizon fixe (avec un taux d'apprentissage constant) et celle basée sur le "truc du doublement", qui ne s'adaptent pas au cadre stochastique plus facile. Enfin, nous déterminons les limites intrinsèques de l'algorithme de Hedge à tout moment dans le cas stochastique, et nous discutons des améliorations apportées par des algorithmes plus adaptatifs.