logo
2.12.17 (744)

Cours scientifiques - APM_5OD2B_TA : Markov decision processes: dynamic programming and applications - part2

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.

15 heures en présentiel

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

Diplôme(s) concerné(s)

Parcours de rattachement

Format des notes

Numérique sur 20

Littérale/grade américain

Pour les étudiants du diplôme M2 DS - Data Science

Le rattrapage est autorisé (Note de rattrapage conservée)
  • le rattrapage est obligatoire si :
    Note initiale < 7
  • le rattrapage peut être demandé par l'étudiant si :
    Note initiale < 7
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 6 ECTS

La note obtenue rentre dans le calcul de votre GPA.

Pour les étudiants du diplôme M2 OPT - Optimisation

Le rattrapage est autorisé (Note de rattrapage conservée)
  • le rattrapage est obligatoire si :
    Note initiale < 7
  • le rattrapage peut être demandé par l'étudiant si :
    Note initiale < 7
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 5 ECTS

La note obtenue rentre dans le calcul de votre GPA.

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