Stratégies de descente miroir pour la minimisation du regret et l’approchabilité
vendredi 2 février 2018, 9h30 - 10h30
Salle du conseil, espace Turing
On présente le modèle d’online linear optimization, qui est un cadre général de minimisation du regret. On y construit une famille de stratégie de « descente miroir » avec paramètres variables. On établit des bornes sur le regret garanties par ces stratégies. Les paramètres variables permettent de retrouver comme cas particuliers un grand nombre de stratégies connues: Exponential Weights Algorithm, Smooth Fictitious Play, Vanishingly Smooth Fictious Play, ainsi que Follow the Perturbed Leader.
Dans un second temps, on suppose que les vecteurs de paiement ont au plus deux composantes non nulles et on cherche à déterminer les bornes optimales sur le regret dans ce cadre. On remarque qu’il apparaît alors une différence fondamentale entre les gains et les pertes.
On présente ensuite une méthode générale pour construire des stratégies pour l’approchabilité de Blackwell à partir des stratégies minimisant le regret. Le caractère unificateur de cette approche est illustrée par l’obtention, en corollaire, des bornes optimales pour les problèmes d’online combinatorial optimization et du regret interne/swap. On établit par ailleurs que la stratégie de Blackwell est un cas particuler de la famille de stratégies ainsi construite.
Enfin, on étudie le problème de l’approchabilité de Blackwell avec observations partielles (c’est-à-dire, où le joueur n’observe que des signaux aléatoires). On établit que la vitesse de convergence optimale est de T^{-1/3}.
