Les Processus Décisionnels de Markov
Cette partie consistera à présenter le cadre théorique des processus de décisions markoviens. En partant de la définition du Processus Décisionnel de Markov, nous allons présenter les différentes familles de politiques et ensuite voir en détail chacun des différents critères utilisés en ce processus.
Définition 2.1. Processus Décisionnel de Markov
Les processus décisionnels de Markov ou en anglais « Markovian decision processes » (MDP) sont définis comme des processus stochastiques contrôlés satisfaisant la propriété de Markov, assignant des récompenses aux transitions d’états. Nous les définissons par un quintuplet (S, A, T , p, r) où :
– S est l’espace d’états dans lequel évolue le processus. S peut être fini ou dénombrable et peut être fonction de l’instant t. Dans toute la suite nous supposerons que S fini.
– A est l’espace des actions ou décisions qui contrôlent la dynamique de l’état. De même A peut être fini ou dénombrable. Dans le cas général, l’espace A peut être dépendant de l’état courant (As pour s ∈ S), peut être fonction de l’instant t. Dans toute la suite, nous nous limiterons au cas où A est fini.
– T est l’espace des temps, il représente le temps.
T est un ensemble discret, assimilé à un sous ensemble de N, qui peut être fini ou infini (on parle d’horizon fini ou d’horizon infini).
– p() sont les probabilités de transition entre états.
Les probabilités de transition caractérisent la dynamique de l’état du système. Pour une action a ∈ A fixée, p(j|i, a) ou pi,j (a) désigne alors la probabilité de transition quand le système se déplace d’un état i ∈ S vers un nouveau état j ∈ S dans la prochaine période du temps observée quand la décision a ∈ A est pris.
– r() est la fonction de récompense (ou aussi le gain, le coût, ou encore le revenu) sur les transitions entre états. C’est à dire rt(s, a) désigne la fonction de récompense quand on a choisi l’action a dans l’état s à l’instant t. rt peut être considérée comme un gain ou sinon un coût selon le contexte étudié.
Les processus décisionnels de Markov intègrent les concepts d’état qui résument la situation de l’agent à chaque instant, et à chaque action (ou décision) qui influence la dynamique de l’état, de revenu (ou récompense) qui est associé à chacune des transitions d’état. Les MDP sont des chaînes de Markov visitant les états, contrôlées par les actions et valuées par les revenus.
Définition 2.2. Politique
Une politique ou stratégie, est une séquence de décisions ou la procédure suivie par l’agent pour choisir à chaque instant l’action à exécuter. Plus précisément, une politique représente le choix d’une action à effectuer dans un état donné. Nous la noterons par π.
Les différentes familles de politiques
Soient S l’espace d’états et A l’espace des actions, tous les deux ensembles finis et discrets et l’espace des temps T avec T ⊆ N. Nous distinguons quatre familles de politiques :
– la politique histoire-dépendante déterministe Cette politique se base sur l’historique ht = (s0, a0, s1, a1, …, st−1, at−1, st) et détermine précisément l’action à effectuer. On la définit comme une fonction :
πHD :Ht → A
ht→ at
où ht = (s0, a0, s1, a1, …, st−1, at−1, st) pour tout t ∈ T avec
Ht = {ht = (s0, a0, s1, a1, …, st−1, at−1, st)|(sk, ak) ∈ S × A; 1 ≤ k ≤ t − 1; st ∈ S}
et S × A = {(s, a)|s ∈ S, a ∈ A}
Critère d’optimalité
Définition 2.7. Critère d’optimalité
Le critère d’optimalité permet de caractériser les politiques qui permettront de générer des séquences de récompenses les plus importantes possibles. La politique optimale est calculée en fonction de la fonction de gain ou de coût : il s’agit d’optimiser les récompenses possibles ou de minimiser les coûts possibles. Nous évaluons une politique sur la base d’une mesure du cumul espéré des récompenses instantanées le long d’une trajectoire. Les critères que nous allons étudiés au sein de ce mémoire sont :
– le critère fini,
– le critère total α-pondéré à horizon infini (discounted infinite horizon reward)
– le critère moyen à horizon infini(average-reward criterion).
Remarque
Pour ces différents critères, lorsque l’on connait l’état initial (ou une distribution de probabilité sur l’état initial), toute politique histoire-dépendante aléatoire peut être remplacée par une politique markovienne aléatoire ayant la même fonction de valeur. La section suivante nous confirme cette relation.
Pour chacun des critères, nous avons ainsi déterminer la spécificité de chaque équation d’optimalité portant sur les fonctions de valeur et nous avons pu avoir la politique optimale. Nous avons eu des systèmes linéaires dans les équations d’optimalité pour chacun des critères. D’une part, dans le cadre du critère fini, les politiques optimales sont donc de type markovien déterministe, mais non stationnaire c’est-à-dire le choix de la meilleure décision à prendre dépend de l’instant t. D’autre part, pour le critère α-pondéré, les politiques optimales sont de type stationnaire et déterministe. Pour le critère moyen, les politiques optimales sont aussi de type stationnaire et déterministe, en outre l’étude est un peu plus complexe que celle des autres, si on veut avoir une vision plus explicite, il faudra classifier les MDP. Cependant, dans la prochaine partie, nous allons nous intéresser uniquement au critère α- pondéré.
Formulation en programmation linéaire
Définition 3.1. Solution
Nous appellons « solution », toutes valeurs spécifiques des variables décisionnelles (x1, x2, …, xn).
Définition 3.2. Solution réalisable
Une solution est appelée une solution réalisable si elle satisfait simultanément toutes les contraintes du problème.
Définition 3.3. Solution extrême
Une solution extrême est une solution qui ne peut pas s’écrire comme une combinaison linéaire de 2 autres solutions.
Définition 3.4. Solution extrême réalisable
Une solution extrême est réalisable si elle satisfait simultanément toutes les contraintes du problème.
Définition 3.5. Solution optimale
Une solution optimale est une solution réalisable ayant la valeur de la fonction objectif la plus favorable.
Définition 3.6. Base
Nous appellons « base » : toutes sous matrices carrés régulières extraites de A. Le complément de B dans A est le hors-base associé.
Définition 3.7. Solution de base .
Soit A = [B, N] , avec B la matrice de base et N la matrice hors base.
Soit ~x = [xB, xN ], avec xB les variables de base et xN les variables hors base . Nous appellons « Solution de base » associé à la matrice de base B la solution particulière de l’équation :
BxB + NxN = b
|
Table des matières
Introduction générale
1 Généralités
2 Les Processus Décisionnels de Markov
2.1 Les différentes familles de politiques
2.2 La fonction de valeur
2.3 Caractéristique d’une politique markovienne
2.4 Critère d’optimalité
2.5 Relation entre les politiques histoires-dépendantes et les politiques markoviennes
2.6 Etude des différentes critères
2.6.1 Critère fini
2.6.2 Critère α−pondéré à horizon infini
2.6.3 Critère moyen : average-reward criterion
3 Formulation en programmation linéaire
3.1 Caractérisation des bases réalisables et des solutions des bases réalisables optimales
3.2 Notion de Dualité en programmation linéaire
3.2.1 Propriétés de la dualité
3.2.2 Théorème fondamental de la dualité
3.3 Formulation d’un MDP en programmation linéaire
3.3.1 Programme linéaire primal
3.3.2 Programme linéaire dual
3.4 La méthode du simplexe
3.4.1 Principes de la méthode du simplexe
3.4.2 Algorithme du simplexe
4 Les Algorithmes « Policy-Iteration » et « Value Iteration »
4.1 Algorithme d’itération sur les valeurs ou « Value Iteration »
4.1.1 Principe de l’algorithme de « Value Iteration »
4.1.2 Algorithme de « Value Iteration »
4.1.3 Convergence de l’algorithme de « Value Iteration »
4.1.4 Complexité de l’algorithme
4.2 Algorithme d’itération sur les politique ou « Policy iteration »
4.2.1 Principe de l’algorithme de « Policy iteration »
4.2.2 Algorithme de « Policy Iteration »
4.2.3 Convergence de l’algorithme de « Policy Iteration »
4.2.4 Complexité de l’algorithme
4.3 Comparaison des deux algorithmes « Value Iteration » et « Policy Iteration »
5 Etude de cas
5.1 Formalisation du problème
5.1.1 Définition de l’ensemble d’états
5.1.2 Définition de l’ensemble d’actions
5.1.3 Définition des récompenses
5.2 Application numérique
5.2.1 état s=0
5.2.2 état s=1
5.2.3 état s=2
5.2.4 état s=3
5.3 Résolution du problème
5.3.1 Résolution par l’Algorithme de « Policy Iteration »
5.3.2 Résolution par l’Algorithme de « Value Iteration »
5.3.3 Résolution par la programmation linéaire
Conclusions générales
