Processus de décision markovien

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un processus de décision markovien (MDP) est un modèle stochastique issu de la théorie de la décision et de la théorie des probabilités. Le modèle MDP peut être vu comme une chaîne de Markov à laquelle on ajoute une composante décisionnelle. Comme les autres modèles de sa famille, il est entre autres, utilisé en intelligence artificielle pour le contrôle de systèmes complexes comme des agents intelligents.

Un MDP permet de prendre des décisions dans un environnement

  • lorsque l'on a une certitude sur l'état dans lequel on se trouve
  • en présence d'incertitude sur l'effet des actions.

Définition[modifier | modifier le code]

Cycle de contrôle d'un processus de décision markovien

Définition intuitive[modifier | modifier le code]

Afin de comprendre ce qu'est un MDP, supposons que l'on ait un système évoluant dans le temps comme un automate probabiliste. À chaque instant le système est dans un état donné et il existe une certaine probabilité pour que le système évolue vers tel ou tel autre état à l'instant suivant en effectuant une transition.

Supposons maintenant que l'on doive contrôler ce système boite noire de la meilleure façon possible. L'objectif est de l'amener dans un état considéré comme bénéfique, en évitant de lui faire traverser des états néfastes. Pour cela, on dispose d'un ensemble d'actions possibles sur le système. Pour compliquer la chose, on supposera que l'effet de ces actions sur le système est probabiliste : l'action entreprise peut avoir l'effet escompté ou un tout autre effet. L'efficacité du contrôle est mesurée relativement au gain ou à la pénalité reçue au long de l'expérience.

Ainsi, un raisonnement à base de MDP peut se ramener au discours suivant : étant dans tel cas et choisissant telle action, il y a tant de chance que je me retrouve dans tel nouveau cas avec tel gain.

Pour illustrer les MDP, on prend souvent des exemples issus de la robotique mobile (avec les positions pour états, les commandes comme actions, les mouvements comme transitions et l'accomplissement/échec de tâches comme gains/pénalités).

Hypothèse de Markov[modifier | modifier le code]

Dans les MDP, l'évolution du système est supposée correspondre à un processus markovien. Autrement dit, le système suit une succession d'états distincts dans le temps et ceci en fonction de probabilités de transitions. L'hypothèse de Markov consiste à dire que les probabilités de transitions ne dépendent que des n états précédents. En général, on se place à l'ordre n = 1, ce qui permet de ne considérer que l'état courant et l'état suivant.

Définition formelle[modifier | modifier le code]

Un MDP est un quadruplet \{ S, A, T, R \}\, où :

  • S = \{ s_0, \cdots , s_{ |S| } \} \, est l'ensemble fini discret des états possibles du système à contrôler
  • A = \{ a_0, \cdots , a_ {|A| } \} \, est l'ensemble fini discret des actions que l'on peut effectuer pour contrôler le système
  • T : S \times A \times S \to [ 0 ; 1 ]\, est la fonction de transition du système en réaction aux actions de contrôle.

Dans le cas général, la fonction T est probabiliste et donne la probabilité p (s' | s, a) = T (s, a, s') \, que le système passe de l'état s à l'état s' lorsque l'on choisit d'effectuer l'action a.

  • R : S \times A \times S \to \Re est la fonction de récompense. Elle indique la valeur réelle obtenue lorsque l'on effectue l'action a dans l'état s pour arriver dans l'état s'.

Exemple de MDP[modifier | modifier le code]

Exemple simple de Processus de Décision Markovien à trois états et à deux actions.

L'exemple donné ci-contre représente un Processus de Décision Markovien à trois états distincts \{ S_0, S_1, S_2 \} représentés en vert. Depuis chacun des états, on peut effectuer une action de l'ensemble \{ a_0, a_1 \}. Les nœuds rouges représentent donc une décision possible (le choix d'une action dans un état donné). Les nombres indiqués sur les flèches sont les probabilités d'effectuer la transition à partir du nœud de décision. Enfin, les transitions peuvent générer des récompenses (dessinées ici en jaune).

  • La matrice de transition associée à l'action a_0 est la suivante :

\begin{pmatrix} 0.50 & 0 & 0.50 \\ 0.70 & 0.10 & 0.20 \\ 0.40 & 0 & 0.60 \end{pmatrix}

  • La matrice de transition associée à l'action a_1 est la suivante :

\begin{pmatrix} 0 & 0 & 1.0 \\ 0 & 0.95 & 0.05 \\ 0.30 & 0.30 & 0.40 \end{pmatrix}

En ce qui concerne les récompenses,

  • on perçoit une récompense de +5 lorsque l'on passe de l'état S_1 à l'état S_0 en accomplissant l'action a_0
  • on perçoit une récompense de -1 (aussi appelée pénalité) lorsque l'on passe de l'état S_2 à l'état S_0 en accomplissant l'action a_1

Remarques[modifier | modifier le code]

Le modèle MDP présenté ici est supposé stable dans le temps, c'est-à-dire que les composants du quadruplet sont supposés invariants. Il n'est donc pas applicable en l'état pour un système qui évolue, par exemple pour modéliser un système qui apprend contre un autre agent.

Notion de stratégie[modifier | modifier le code]

Dans le cadre des MDP, la stratégie \pi : S \to A est une suite qui indique pour chaque état quelle est l'action à effectuer. Il s'agit là d'une stratégie déterministe, dans laquelle il n'y a pas d'ambiguïté sur l'action à effectuer. On note \Pi l'ensemble des stratégies déterministes.

Note : Il est possible d'introduire du hasard dans le choix de l'action, comme si on tirait aléatoirement l'action à effectuer. Dans ce cas, on parlera de stratégie stochastique \pi : S \times A \to [ 0 ; 1 ].

Problèmes possibles[modifier | modifier le code]

  • Planification : Il s'agit, étant donné un MDP \{ S, A, T, R \} de trouver quelle est la politique \pi qui maximise la récompense,
  • Améliorer une politique connue : Soit une politique \pi_0, on souhaite trouver une meilleure politique,
  • Apprentissage d'une politique sans connaitre le modèle
    • à partir de traces d'exécution
    • au cours d'expériences sur le modèle

Algorithmes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Voir aussi :

Bibliographie[modifier | modifier le code]

Références[modifier | modifier le code]