Le manuscrit se divise en deux parties. La première est constituée des chapitres I à IV et propose une présentation unifiée de nombreux résultats connus ainsi que de quelques éléments nouveaux. On présente dans le Chapitre I le problème d’online linear optimization, puis on construit les stratégies de descente miroir avec paramètres variables pour la minimisation du regret, et on établit dans le Théorème I.3.1 une borne générale sur le regret garantie par ces stratégies. Ce résultat est fondamental car la quasi-totalité des résultats des quatre premiers chapitres en seront des corollaires. On traite ensuite l’extension aux pertes convexes, puis l’obtention d’algorithmes d’optimisation convexe à partir des stratégies minimisant le regret. Le ChapitreII se concentre sur le cas où le joueur dispose d’un ensemble fini dans lequel il peut choisir ses actions de façon aléatoire. Les stratégies du Chapitre I sont aisément transposées dans ce cadre, et on obtient également des garanties presquesûres d’une part, et avec grande probabilité d’autre part. Sont ensuite passées en revue quelques stratégies connues : l’Exponential Weights Algorithm, le Smooth Fictitious Play, le Vanishingly Smooth Fictitious Play, qui apparaissent toutes comme des cas particuliers des stratégies construites au Chapitre I. En fin de chapitre, on mentionne le problème de bandit à plusieurs bras, où le joueur n’observe que le paiement de l’action qu’il a jouée, et on étudie l’algorithme EXP3 qui est une adaptation de l’Exponential Weights Algorithm dans ce cadre. Le Chapitre III est consacré à la classe de stratégies appelée Follow the Perturbed Leader, qui est définie à l’aide de perturbations aléatoires. Un récent survey [ALT16] mentionne le fait que ces stratégies, bien que définies de façon différente, appartiennent à la famille de descente miroir du Chapitre I. On donne une démonstration détaillée de ce résultat. Le Chapitre IV a pour but la construction de stratégies de descente miroir pour l’approchabilité de Blackwell. On étend une approche proposée par [ABH11] qui permet de transformer une stratégie minimisant le regret en une stratégie d’approchabilité. Notre approche est plus générale car elle permet d’obtenir des bornes sur une très large classe de quantités mesurant l’éloignement à l’ensemble cible, et non pas seulement sur la distance euclidienne à l’ensemble cible. Le caractère unificateur de cette démarche est ensuite illustrée par la construction de stratégies optimales pour le problème d’online combinatorial optimization et la minimisation du regret interne/swap. Par ailleurs, on démontre que la stratégie de Backwell peut être vue comme un cas particulier de descente miroir. La seconde partie est constituée des quatre articles suivants, qui ont été rédigés pendant la thèse. Le ChapitreVest tiré de l’article [KP16b] et étudie le problème de la minimisation du regret dans le cas où le joueur possède un ensemble fini d’actions, et avec l’hypothèse supplémentaire que les vecteurs de paiement possèdent au plus s composantes non-nulles. On établit, en information complète, que la borne optimale sur le regret est de l’ordre de √Tlog s (où T est le nombre d’étapes) lorsque les paiements sont des gains (c’est-à-dire lorsqu’ils sont positifs), et de l’ordre de √Ts log d d (où d est le nombre d’actions) lorsqu’il s’agit de pertes (i.e. négatifs). On met ainsi en évidence une différence fondamentale entre les gains et les pertes. Dans le cadre bandit, on établit que la borne optimale pour les pertes est de l’ordre de √ Ts à un facteur logarithmique près. Le Chapitre VI est issu de l’article [KP16a] et porte sur l’approchabilité de Blackwell avec observations partielles, c’est-à-dire que le joueur observe seulement des signaux aléatoires. On construit des stratégies garantissant des vitesses de convergence de l’ordre de O(T−1/2 ) dans le cas de signaux dont les lois ne dépendent pas de l’action du joueur, et de l’ordre de O(T−1/3 ) dans le cas général. Cela établit qu’il s’agit là des vitesses optimales car il est connu qu’on ne peut les améliorer sans hypothèse supplémentaire sur l’ensemble cible ou la structure des signaux. Le Chapitre VII est tiré de l’article [KM14] et définit les stratégies de descente miroir en temps continu. On établit pour ces derniers une propriété de non-regret. On effectue ensuite une comparaison entre le temps continu et le temps discret. Cela offre une interprétation des deux termes qui constituent la borne sur le regret en temps discret : l’un vient de la propriété en temps continu, l’autre de la comparaison entre le temps continu et le temps discret. Enfin, le ChapitreVIIIest indépendant et est issu de l’article [Kwo14]. On y établit une borne universelle sur les variations des fonctions convexes bornées. On obtient en corollaire que toute fonction convexe bornée est lipschitzienne par rapport à la métrique de Hilbert.