v2.11.0 (5354)

Cours scientifiques - OROC-OP-DP : Markov decision processes: dynamic programming and applications

Domaine > Analyse et Calcul Scientifique, 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 <a href="http://www;scilab.org/">Scilab</a>.
Ce cours est fait en commun avec le master <a href="http://webens.math.u-psud.fr/-optimization-"><b>Optimization</b></a> 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.

Il sera donné en anglais.

34 heures en présentiel (13 blocs ou créneaux)
réparties en:
  • Contrôle : 3
  • Travaux dirigés en salle info : 2
  • Stage de communication : 29

Diplôme(s) concerné(s)

Parcours de rattachement

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 :

 Final exam + practical works.

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.5

La note obtenue rentre dans le calcul de votre GPA.

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

Programme détaillé

1. Bloc de module:
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. Bloc de module:
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. Bloc de module:
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. Bloc de module:
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. Bloc de module:
Long-term behaviour of Markov chains: recurrence, invariant measure, ergodic theorem.  Evaluation of mean-payoff/ergodic criteria or long-term risk sensitive criteria.
6. TD:
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. Bloc de module:
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. Bloc de module:
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. Bloc de module:
Constrained MDP. Formulation in terms of occupation measures and linear programming. Relaxed strategies.
10. Bloc de module:
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. Bloc de module:
Problems with partial observation: reduction to a MDP with an infinite state space. The dynamic programming equation.
12. Bloc de module:
Gittins index for multiarmed bandits.
13. Contrôle: 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