Mathematics of Statistical Sequential Decision Making

In this document, we give an overview of recent contributions to the mathematics of statistical sequential learning. Unlike research articles that start from a motivating example and provide little room to the mathematical tools in the main body of the article, we here give primary focus to these tools, in order to stress their potential as well as their role in the development of improved algorithms and proof techniques in the field. We revisit inparticular properties of the log Laplace transform of a random variable, the handling of random stopping time in concentration of measure of empirical distributions, and we highlight the fundamental role of the “change of measure” argument both in the construction of performance lower-bounds as well as near-optimal strategies. We then give focus to obtaining finite-time error guarantees on the parameter estimation in parametric models before highlighting the strength of Legendre-Fenchel duality in the design of risk-averse and robust strategies. Finally, we turn the setting of Markov decision processes where we present some key insights for the development of the next generation of decision strategies. We end this manuscript by providing a more focused presentation of three key contributions in bandit theory, stochastic automata, and aggregation of experts.Ce document montre un tour d’horizon de quelques contributions récentes à la mathématique de l’apprentissage statistique séquentiel. Contrairement aux articles de recherches qui partent d’exemples et donnent peu de place aux outils mathématiques, souvent relayés en annexe, nous présentons ici ces outils en pleine lumière, afin de souligner leur rôle capital dans le développement de nouvelles stratégies de prise de décision séquentielle dans l’incertain. Nous revisitons en particulier les propriétés de la transformée de Laplace d’une variable aléatoire, la prise en compte des temps d’arrêt pour la concentration de distributions empiriques, avant de souligner le rôle fondamental du "changement de mesure" dans la construction à la fois des meilleures bornes de performances atteignables et des stratégies quasi-optimales. Nous nous tournons ensuite vers l’obtention de bornes d’erreuren temps fini pour l’estimation de paramètre dans différents modèles paramétriques, avant d’expliquer le rôleclé de la dualité de Legendre-Fenchel dans la construction de stratégies robustes et sensibles au risque. Enfin, nous présentons, dans le cadre des processus décisionnels de Markov, de nouveaux éléments de compréhension utiles à la découverte de nouvelles stratégies de prise de décision séquentielle. Ce manuscrit se termine par une présentation plus détaillée de trois contributions clés à la théorie de bandits, aux automates stochastiques ainsi qu’à l’agrégation d’experts