Processus décisionnels de Markov

Les processus décisionnels de Markov formalisent la prise de décision séquentielle, modélisant un agent qui choisit des actions dans des états afin de maximiser une récompense à long terme.

Definition

Un processus décisionnel de Markov est un modèle de prise de décision séquentielle défini par un ensemble d'états, d'actions disponibles, de probabilités de transition entre les états étant donné les actions, et de récompenses, dans lequel l'objectif est de trouver une politique qui maximise la récompense cumulée actualisée attendue.

Scope

Ce sujet couvre le cadre mathématique sous-jacent à l'apprentissage par renforcement : les états, les actions, les probabilités de transition, les récompenses et le facteur d'actualisation ; les politiques et les fonctions de valeur ; les équations d'optimalité de Bellman ; et les méthodes de programmation dynamique d'itération de la valeur et d'itération de la politique qui résolvent un processus connu. Il suppose la propriété de Markov selon laquelle l'avenir ne dépend que de l'état actuel.

Core questions

• Quels sont les composants qui définissent un processus décisionnel de Markov ?
• Comment les équations de Bellman relient-elles la valeur d'un état à ses successeurs ?
• Comment l'itération de la valeur et l'itération de la politique trouvent-elles des politiques optimales ?
• Que suppose la propriété de Markov concernant l'environnement ?

Key theories

Équations d'optimalité de Bellman

La valeur d'une action optimale à partir d'un état est égale à la meilleure récompense immédiate plus la valeur actualisée de l'état résultant, une relation récursive dont la solution définit la politique optimale.

Programmation dynamique

Lorsque le processus est entièrement connu, l'itération de la valeur et l'itération de la politique calculent des fonctions de valeur et des politiques optimales en appliquant de manière répétée la mise à jour de Bellman, garantissant la convergence vers l'optimum.

Actualisation et rendement

Les récompenses futures sont pondérées par un facteur d'actualisation afin que le rendement total soit bien défini et que les récompenses plus proches comptent davantage, influençant ainsi la portée effective de la planification de l'agent.

Clinical relevance

Les processus décisionnels de Markov constituent la colonne vertébrale conceptuelle de l'apprentissage par renforcement et d'une grande partie de la recherche opérationnelle et du contrôle, fournissant le langage des états, des actions et de la valeur que presque tous les algorithmes d'apprentissage approximent lorsque le modèle est inconnu ou trop vaste pour être résolu exactement.

History

Le cadre est issu de la programmation dynamique de Bellman dans les années 1950 et des travaux d'itération de politique de Howard, fournissant des méthodes de solution exactes pour les processus décisionnels connus. L'apprentissage par renforcement a ensuite adopté le processus décisionnel de Markov comme son formalisme standard pour le cas où les transitions et les récompenses doivent être apprises par l'expérience.

Key figures

• Richard Bellman
• Ronald Howard
• Richard Sutton

Seminal works

• sutton2018
• bellman1957
• puterman1994

Frequently asked questions

Qu'est-ce que la propriété de Markov ?

La propriété de Markov stipule que l'évolution future du processus ne dépend que de l'état et de l'action actuels, et non de l'historique complet de la manière dont l'agent y est parvenu. Cela fait de l'état actuel un résumé suffisant pour la prise de décision.

Pourquoi utilise-t-on un facteur d'actualisation ?

L'actualisation pondère plus fortement les récompenses proches que les récompenses lointaines. Elle maintient le rendement total fini sur des horizons longs ou infinis et encode une préférence pour une récompense plus rapide, tout en contrôlant la portée effective de la planification de l'agent dans le futur.