v2.11.0 (5354)

Cours scientifiques - SOD312 : Markov decision processes: dynamic programming and applications

Domaine > Optimisation, Recherche opérationnelle et Commande, Mathématiques et leurs applications.

Descriptif

Le but de ce cours est de présenter la théorie et quelques applications de la méthode de la programmation dynamique en environnement stochastique.
A la fin du cours, les élèves devront pouvoir formuler un problème d'optimisation stochastique, en caractériser les solutions, étudier leur complexité et trouver éventuellement des solutions sous-optimales.
Le cours est illustré par des travaux pratiques en salle informatique, à l'aide du logiciel Scilab.
 
Ce cours est fait en commun avec le M2 Optimization de l'Université Paris-Saclay .
- les 18 premières heures du cours constituent la partie ENSTA du cours,
- les 12 heures suivantes sont des compléments apportés dans le cadre du Master,
- l'examen commun a lieu lors de la dernière séance.
 
Les élèves de l'ENSTA ne suivant pas un M2 en parallèle de ce parcours sont fortement encouragés à suivre la totalité du cours.

Le cours sera donné en anglais.

Objectifs pédagogiques

Comprendre et utiliser la programmation dynamique déterministe et stochastique.

21 heures en présentiel

50 heures de travail personnel estimé pour l’étudiant.

effectifs minimal / maximal:

10/50

Diplôme(s) concerné(s)

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées

Théorie de l'optimisation. Théorie des probabilités et chaînes de Markov.

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées

Vos modalités d'acquisition :

 Examen écrit.

Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)
  • le rattrapage est obligatoire si :
    Note initiale < 6
  • le rattrapage peut être demandé par l'étudiant si :
    6 ≤ note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 1.5 ECTS
  • Scientifique acquis : 1.5

Le coefficient de l'UE est : 1

La note obtenue rentre dans le calcul de votre GPA.

L'UE est évaluée par les étudiants.

Programme détaillé

1. Dynamic programming equation of deterministic control problems.
Markov chains: Fokker-Planck and Kolmogorov equations, graph and communication classes. Problems with additive or  discounted criteria, with constant or non constant discount factors, and with finite horizon.
2. Markov chains: stopping time, strong Markov property. Problems with additive or  discounted criteria, and stopping time or infinite horizon. Equivalence between criteria with discount factors and criteria with stopping time.
Homogeneous Markov chains: forward Kolmogorov equation, reduction to a sequence of i.i.d. random variables.
3. Introduction to Markov decision processes (MDP) with complete state observation.
Problems with additive or discounted criteria and finite horizon, with or without an exit time. Markovian strategies, feedback policies given by the dynamic programming equation.
Properties of the dynamic programming operator (monotonicity, homogeneity, sup-norm nonexpansivity, convexity).
4. MDP with infinite horizon. Contraction of the dynamic programming operator. Application to the dynamic programming equation and to the convergence of value iteration and policy iteration algorithms.
5. Long-term behaviour of Markov chains: recurrence, invariant measure, ergodic theorem.  Evaluation of mean-payoff/ergodic criteria or long-term risk sensitive criteria.
6. Practical work on the PageRank optimization. This practical work will informally use results which will be developed in next lectures.
Training session on dynamic programming with finite horizon: a Dam management problem.
7. Modelization and solution of several problems among stock management, machine maintenance, portfolio selection, Yield management, transportation, PageRank optimisation.
The aim of this lecture is to illustrate the techniques of the previous lectures, and also to motivate the introduction of new ones, which will be partly studied in the following lectures.
End of the ENSTA program.
8. MDP with mean-payoff/ergodic criteria or long-term risk sensitive criteria: ergodic dynamic programming equation, vanishing discount approach.
The irreducible or unichain case: existence and uniqueness of a solution, value and policy iterations.
9. Constrained MDP. Formulation in terms of occupation measures and linear programming. Relaxed strategies.
10. Introduction to multichain  mean-payoff MDP and/or to zero-sum games associated to risk sensitive criteria, and/or  Max-plus algebra for deterministic control problems.
11. Problems with partial observation: reduction to a MDP with an infinite state space. The dynamic programming equation.
12. Gittins index for multiarmed bandits.
13. Control:  written exam

Mots clés

Markov Decision processes, Stochastic control, Ergodic control, Risk-sensitive control, Dynamic programming, Max-plus algebra, Value iteration, Policy iteration
Veuillez patienter