Processus de décision markovien

En théorie de la décision et de la théorie des probabilités, un processus de décision markovien (en anglais Markov decision process, MDP) est un modèle stochastique où un agent prend des décisions et où les résultats de ses actions sont aléatoires. Les MDPs sont utilisés pour étudier des problèmes d'optimisation à l'aide d'algorithmes de programmation dynamique ou d'apprentissage par renforcement. Les MDPs sont connus depuis les années 1950. Une grande contribution provient du travail de Ronald A. Howard avec son livre de 1960, Dynamic Programming and Markov Processes. Ils sont utilisés dans de nombreuses disciplines, notamment la robotique, l'automatisation, l'économie et l'industrie manufacturière. Un processus de décision markovien est un processus de contrôle stochastique discret. À chaque étape, le processus est dans un certain état et l'agent choisit une action . La probabilité que le processus arrive à l'état est déterminée par l'action choisie. Plus précisément, elle est décrite par la fonction de transition d'états . Donc, l'état dépend de l'état actuel et de l'action sélectionnée par le décideur. Cependant, pour un et un , le prochain état est indépendant des actions et états précédents. On dit alors que le processus satisfait la propriété de Markov. Quand le processus passe de l'état à l'état avec l'action , l'agent gagne une récompense . Les MDPs sont une extension des chaînes de Markov. La différence est l'addition des actions choisies par l'agent et des récompenses gagnées par l'agent. S'il n'y a qu'une seule action à tirer dans chaque état et que les récompenses sont égales, le processus de décision markovien est une chaîne de Markov. 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.