Stratégies de descente miroir pour la minimisation du regret et l’approchabilité

The manuscript is divided in two parts. The first consists in Chapters I to IV and offers a unified presentation of numerous known results as well as some new elements. We present in Chapter I the online linear optimization problem, then construct Mirror Descent strategies with varying parameters for regret minimization, and establish in Theorem I.3.1 a general bound on the regret guaranteed by the strategies. This result is fundamental, as most of the results from the first four chapters will be obtained as corollaries. We then deal with the extension to convex losses, and with the derivation of convex optimization algorithms from regret minimizing strategies. Chapter II focuses on the case where the Decision Maker has a finite set from which he can pick his actions at random. The strategies from Chapter I are easily transposed to this framework and we also obtain high-probability and almost-sure guarantees. We then review a few known strategies: Exponential Weights Algorithm, Smooth Fictitious Play, and Vanishingly Smooth Fictitious Play, which all appear as special cases of the strategies constructed in Chapter I. At the end of the chapter, we mention the multi-armed bandit problem, where the Decision Maker only observes the payoff of the action he has played. We study the EXP3 strategy, which is an adaptation of the Exponential Weights Algorithm to this setting. Chapter III is dedicated to the family of strategies called Follow the Perturbed Leader, which is defined using random perturbations. A recent survey [ALT16] mentions the fact that those strategies, although defined differently, actually belong to the family of Mirror Descent strategies from Chapter I. We give a detailed proof of this result. Chapter IV aims at constructing Mirror Descent strategies for Blackwell’s approachability. We extend an approach proposed by [ABH11] that turns a regret minimizing strategy into an approachability strategy. Our construction is more general, as it provides bounds for a very large class of distance-like quantities which measure the “distance” to the target set and not only on the Euclidean distance to the target set. The unifying character of this approach is then illustrated by the construction of optimal strategies for online combinatorial optimization and internal/swap regret minimization. Besides, we prove that Blackwell’s strategy can be seen as a special case of Mirror Descent. The second part of the manuscript contains the following four papers. Chapter V is from [KP16b] and studies the regret minimization problem in the case where the Decision Maker has a finite set of actions, with the additional assumption that payoff vectors have at most s nonzero components. We establish, in the full information setting, that the minimax regret is of order√Tlog s(whereTis the number of steps) when payoffs are gains (i.e nonnegative), and of order √Ts log d d (where d is the number of actions) when the payoffs are losses (i.e. nonpositive). This demonstrates a fundamental difference between gains and losses. In the bandit setting, we prove that the minimax regret for losses is of order √ Ts up to a logarithmic factor. Chapter VI is extracted from [KP16a] and deals with Blackwell’s approachability with partial monitoring, meaning that the Decision Maker only observes random signals. We construct strategies which guarantee convergence rates of order O(T−1/2 ) in the case where the signal does not depend on the action of the Decision Maker, and of order O(T−1/3 ) in the case of general signals. This establishes the optimal rates in those two cases, as the above rates are known to be unimprovable without further assumption on the target set or the signalling structure. Chapter VII comes from [KM14] and defines Mirror Descent strategies in continuous time. We prove that they satisfy a regret minimization property. We then conduct a comparison between continuous and discrete time. This offers an interpretation of the terms found in the regret bounds in discrete time: one is from the continuous time property, and the other comes from the comparison between continuous and discrete time. Finally, Chapter VIII is independent and is from [Kwo14]. We establish a universal bound on the variations of bounded convex function. As a byproduct, we obtain that every bounded convex function is Lipschitz continuous with respect to the Hilbert metric.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