Le domaine de l'apprentissage par renforcement (RL) a connu plusieurs applications réussies au cours de la dernière décennie : du spectaculaire algorithme AlphaGo qui a gagné contre le champion du monde de Go, à la compression vidéo sur Youtube ou à l'optimisation du covoiturage sur des applications de type Uber en Chine. Dans cet exposé, je présenterai le RL d'un point de vue théorique, sous l'angle des Processus de Décision Markoviens (PDM) tabulaires. En particulier, je présenterai deux algorithmes courants pour résoudre les PDM, chacun avec une approche différente : l'un est basé sur un modèle (model-based) et l'autre est sans modèle (model-free). Enfin, je discuterai les limites des garanties théoriques de ces algorithmes, qui sont souvent du type pire-cas, et je montrerai certains des résultats que j'ai prouvés au cours de mon doctorat, qui tentent de surmonter ces limites.
