Victor Boone

Résumé :
Cette thèse est dédiée à la minimisation du regret dans les processus de décisions Markoviens en gain moyen. Le problème y est résolu au premier ordre dans deux cadres fréquentistes classiques : le cas où le modèle est fixé et où la borne dépend du modèle, et le cas minimax où la borne s’applique uniformément à l’intégralité de la classe d'instances considérées. Dans ces deux cadres, on dérive des bornes inférieures sur le regret en espérance, ainsi que des algorithmes atteignant les-dites bornes et de ce fait optimaux. Au delà de la seule minimisation du regret, on étudie également le comportement local d’algorithmes classiques que le regret échoue à capturer, puisque intrinsèquement global. De nouvelles mesures de performances sont introduites dans cette optique et des techniques sont proposés pour circonvenir aux défaults des algorithmes standards.