Processus de décision markovien

Un processus de décision markovien aussi nommé problème de décision markovien est un modèle stochastique issu de la théorie de la décision et de la théorie des probabilités.



Catégories :

Décision - Statistiques - Intelligence artificielle - Processus stochastique - Physique statistique

Page(s) en rapport avec ce sujet :

  • Processus de Décision Markovien. ··· alias MDP (Markov Decision Process). Soient. S un ensemble fini d'états. A un ensemble fini d'actions... (source : asi.insa-rouen)
  • Objectifs. Comprendre la théorie des processus de décision Markovien. Comprendre l'algorithme de résolution du problème de plus court chemin stochastique.... (source : eleves.dptmaths.ens-cachan)
  • UN EXEMPLE DE PROCESSUS DE DÉCISION MARKOVIEN. On souhaite maximiser le revenu provenant de la production d'une machine. Or, ... (source : iro.umontreal)

Un processus de décision markovien (MDP) aussi nommé problème de décision markovien 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 dispositifs complexes comme des agents intelligents.

Un MDP sert à prendre des décisions dans un environnement

Définition

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

Définition intuitive

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

Supposons à présent qu'on doive contrôler ce dispositif boite noire de la meilleure façon envisageable. L'objectif est de l'amener dans un état reconnu comme bénéfique, en évitant de lui faire traverser des états néfastes. Pour cela, on dispose d'un ensemble d'actions envisageables sur le dispositif. Pour compliquer la chose, on supposera que l'effet de ces actions sur le dispositif est probabiliste : l'action entreprise peut avoir l'effet escompté ou un tout autre effet. L'efficacité du contrôle est mesurée assez 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 fréquemment 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

Dans les MDP, l'évolution du dispositif est supposée correspondre à un processus markovien. C'est à dire, le dispositif suit une succession d'états différents dans le temps et ceci selon probabilités de transitions. L'hypothèse de Markov consiste à dire que les probabilités de transitions ne dépendent que des n états qui ont précédé. Généralement, on se place à l'ordre n = 1, ce qui sert à ne considérer que l'état courant et l'état suivant.

Définition formelle

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

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 dispositif passe de l'état s à l'état s' quand on choisit d'effectuer l'action a.

Exemple de MDP

Exemple simple de Processus de Décision Markovien à trois états ainsi qu'à deux actions.

L'exemple donné ci-contre représente un Processus de Décision Markovien à trois états différents {S0, S1, S2} représentés en vert. Depuis chacun des états, on peut effectuer une action de la totalité {a0, a1}. Les nœuds rouges représentent par conséquent une décision envisageable (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).

\begin{pmatrix} 0P & 0 & 0P \\ 0p & 0 & 0  \\ 0@ & 0 & 0` \end{pmatrix}

\begin{pmatrix} 0 & 0 & 1.0 \\ 0 & 0? & 0 \\ 00 & 00 & 0@ \end{pmatrix}

En ce qui concerne les récompenses,

Remarques

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 par conséquent pas applicable en l'état pour un dispositif qui évolue, par exemple pour modéliser un dispositif qui apprend contre un autre agent.

Notion de politique

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

Note : Il est envisageable 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 politique stochastique \pi : S \times A \to [ 0 ; 1 ]

Problèmes envisageables

Références

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Processus_de_d%C3%A9cision_markovien.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu