Descriptif

Objectifs

•  Connaître le cadre des bandits stochastiques à nombre fini de bras, et le cadre de la prévision de suites arbitraires par agrégation de prédicteurs
• Maîtriser les techniques de preuves de bornes inférieures sur le regret
• Maîtriser les techniques de preuves de bornes supérieures sur le regret

Descriptif du cours

Ce cours est un cours très technique, centré sur les preuves mathématiques ; aucune programmation d’algorithmes ne sera proposée, uniquement des preuves, parfois longues et douloureuses. L’objectif est d’apprendre à poser et modéliser un problème d’apprentissage séquentiel, d’exhiber des algorithmes si possible computationnellement efficaces pour majorer le regret, et de montrer ensuite l’optimalité des bornes obtenues, en prouvant
qu’aucun autre algorithme ne peut faire mieux en un sens à préciser.

Cette démarche (modélisation, algorithme pour la borne supérieure, borne inférieure universelle) est la démarche canonique pour publier des résultats sur un problème donné.

Nous verrons également comment rédiger élégamment des preuves. Ce cours est donc fort intéressant pour ceux qui se destinent à une thèse de mathématiques (et ceux-là uniquement).

Prérequis

Une maîtrise et du recul sur les sujets suivants (attention, avoir suivi juste quelques heures de cours sur ces sujets n’est pas suffisant) :

• Théorie de la mesure (ex : lemme de la classe monotone, théorème de Radon-Nykodym)
• Théorie de l’intégration (ex : théorèmes de Fubini)
• Calcul des probabilités (ex : espérances conditionnellement à un vecteur de variables aléatoires)
• Théorie des martingales (ex : théorèmes de Doob pour les sur- ou sous-martingales)
• Notions élémentaires de statistique (ex : intervalles de confiance non-asymptotiques à la Hoeffding)
• Eléments de théorie de l’information idéalement (ex : divergence de Kullback-Leibler, lemme de Pinsker)

Note finale 

La validation du cours se fera par un examen à mi-parcours et un examen final, chacun en 3h environ. Il n’est pas possible de remplacer l’examen par un projet, ce cours étant théorique.