Méthodes approchées

Connaissance de base en algorithmique et probabilité. Un premier contact avec programmation dynamique via le problème de plus court chemin sera un plus.

Programmation dynamique, processus de décisions discrètes de Markov, apprentissage par renforcement.

Le cours présente des méthodes approchées pour les problèmes de décisions discrètes séquentielles optimales. Après quelques rappels de la programmation dynamique et le principe d’optimalité de Bellman, on aborde les concepts de base d’un processus de décisions de Markov : état, actions, politique, fonction de valeur, probabilité de transition, récompense, etc. On décrit ensuite la recherche de la politique optimale dans un processus de Markov par la programmation dynamique. Enfin, on présente des méthodes d’apprentissage par renforcement (Monte-Carlo, TD-learning, Q-learning, …) pour approximer la politique optimale pour le cas non-déterministe lorsque les probabilités de transition et/ou les récompenses ne sont pas connues.

Programmation dynamique, processus de décisions discrètes de Markov, apprentissage par renforcement.