Un processus de décision markovien (PDM) est un modèle mathématique pour la prise de décision séquentielle lorsque les résultats sont incertains. C'est un type de processus de décision stochastique, souvent résolu à l'aide de méthodes de programmation dynamique stochastique. Originaire de la recherche opérationnelle dans les années 1950, les PDM ont depuis gagné en reconnaissance dans des domaines tels que l'écologie, l'économie, la santé, les télécommunications et l'apprentissage par renforcement. Dans l'apprentissage par renforcement, le cadre du PDM modélise l'interaction entre un agent apprenant et son environnement, caractérisée par des états, des actions et des récompenses, fournissant une représentation simplifiée des éléments clés des défis de l'intelligence artificielle, y compris la cause et l'effet, l'incertitude et les objectifs explicites.
Le nom dérive de sa connexion avec les chaînes de Markov, développées par le mathématicien russe Andreï Markov. La propriété « markovienne » fait référence à la structure sous-jacente où les transitions d'état ne dépendent que de l'état et de l'action actuels, et non de l'historique antérieur. Le processus est appelé « processus de décision » car il implique de prendre des décisions qui influencent ces transitions, étendant les chaînes de Markov à la prise de décision sous incertitude.
Définition formelle
Un PDM est généralement défini comme un 4-uplet \((S, A, P_a, R_a)\), où :
- \(S\) est l'espace d'états, qui peut être discret ou continu (par exemple, l'ensemble des nombres réels).
- \(A\) est l'espace d'actions, avec \(A_s\) désignant l'ensemble des actions disponibles depuis l'état \(s\). Cet ensemble peut également être discret ou continu.
- \(P_a(s, s')\) est la probabilité de transition que l'action \(a\) dans l'état \(s\) au temps \(t\) mène à l'état \(s'\) au temps \(t+1\). Pour les états discrets, \(P_a(s, s') = \Pr(s_{t+1} = s' \mid s_t = s, a_t = a)\). Pour les espaces d'états continus, la probabilité est définie via une intégrale, souvent par rapport à la mesure de Lebesgue.
- \(R_a(s, s')\) est la récompense immédiate (ou récompense attendue) reçue après avoir pris l'action \(a\) pour passer de \(s\) à \(s'\). La récompense est généralement une variable aléatoire.
Une fonction de politique \(\pi\) est une application (potentiellement probabiliste) de l'espace d'états vers l'espace d'actions, spécifiant quelle action prendre dans chaque état.
Objectif d'optimisation
L'objectif dans un PDM est de trouver une politique \(\pi\) qui maximise une fonction cumulative des récompenses aléatoires, typiquement la somme actualisée attendue sur un horizon infini : \(\mathbb{E}[\sum_{t=0}^{\infty} \gamma^t R_{a_t}(s_t, s_{t+1})]\), où \(\gamma \in [0, 1)\) est un facteur d'actualisation. Une fois une politique fixée, le PDM se comporte comme une chaîne de Markov, car l'action dans chaque état est déterminée par \(\pi(s)\).
Les méthodes de résolution courantes incluent des techniques de programmation dynamique telles que l'itération de valeur et l'itération de politique, qui calculent des fonctions de valeur ou des politiques optimales. Ces méthodes sont fondamentales dans les algorithmes de apprentissage par renforcement comme Q-learning et SARSA.
Applications
Les PDM sont largement appliqués dans divers domaines. En économie, ils modélisent les décisions optimales de consommation et d'investissement. En santé, ils guident la planification des traitements sous incertitude, comme la gestion des maladies chroniques. En télécommunications, ils optimisent l'allocation des ressources et le routage réseau. En écologie, ils informent les stratégies de conservation pour la gestion des espèces. En apprentissage automatique, les PDM sont centraux dans l'apprentissage par renforcement, permettant aux agents d'apprendre par interaction avec les environnements, comme on le voit en robotique, dans les jeux et les systèmes autonomes.
Relation avec l'apprentissage par renforcement
L'apprentissage par renforcement (RL) utilise le cadre du PDM pour formaliser l'interaction agent-environnement. Dans le RL, l'agent ne connaît pas à l'avance les probabilités de transition ou les fonctions de récompense ; il apprend plutôt une politique optimale par essais et erreurs, en utilisant des échantillons de l'environnement. Cela distingue le RL de la résolution classique des PDM, qui suppose des paramètres de modèle connus. Le RL moderne, y compris l'apprentissage par renforcement profond, combine les PDM avec des approximateurs de fonctions basés sur des réseaux de neurones pour gérer de grands espaces d'états, comme démontré dans des applications telles que les jeux et la conduite autonome.
Extensions et variations
Plusieurs extensions abordent les limites du PDM de base. Les processus de décision markoviens partiellement observables (POMDP) gèrent les situations où l'agent ne peut pas observer directement l'état complet. Les PDM factorisés exploitent la structure des variables d'état pour améliorer l'évolutivité. Les PDM multi-agents étendent le cadre à plusieurs décideurs avec des objectifs interactifs. Ces variations conservent la propriété markovienne centrale tout en s'adaptant à des problèmes du monde réel plus complexes.
Contexte historique
La formalisation des PDM est attribuée à Richard Bellman dans les années 1950, qui a également développé la programmation dynamique. Les travaux antérieurs d'Andreï Markov sur les processus stochastiques ont fourni la base théorique. Depuis lors, les PDM sont devenus une pierre angulaire de la recherche opérationnelle et de l'intelligence artificielle, influençant à la fois les travaux théoriques et appliqués dans la prise de décision séquentielle.