Modèle formel pour des problèmes de décision séquentielle où un agent observe un état, choisit une action et le système passe à un état suivant selon des probabilités de transition dépendant uniquement de l’état courant et de l’action (propriété de Markov) ; une fonction de récompense attribue des gains immédiats et l’objectif est de maximiser la récompense cumulée espérée sur un horizon (actualisé ou fini).

Principe

Le contrôle optimal est caractérisé par l’optimalité de Bellman : la fonction de valeur satisfait une équation récursive qui égalise la valeur d’un état à la meilleure espérance de récompense immédiate plus la valeur actualisée des états successeurs ; résoudre ces équations (itération sur la valeur, itération sur la politique, programmation linéaire) fournit une politique optimale si les espaces et les probabilités sont connus et tractables.

Démonstration

Scénario illustratif — Réapprovisionnement d’un stock : Situation — état = niveau de stock, action = quantité à commander, la demande est stochastique de loi connue. Reconnaissance — définir P(s'|s,a) à partir du modèle de demande et le coût immédiat (stockage, rupture, commande). Action — exécuter l’itération de valeur : initialiser la valeur, appliquer la mise à jour de Bellman jusqu’à convergence, extraire la politique. Conséquence — la politique obtenue minimise le coût attendu à long terme sous le modèle et l’actualisation choisis, sous réserve de la validité du modèle et des limites computationnelles.

Mauvaise application

Traiter un problème partiellement observable ou dépendant de l’histoire comme un MDP sans augmenter l’état pour capturer l’information nécessaire, ou considérer une politique apprise comme optimale alors que probabilités de transition ou fonctions de récompense sont mal spécifiées ; l’erreur est de supposer la propriété de Markov ou la connaissance du modèle là où elles n’existent pas.

Conséquence

Bien spécifié, un MDP fournit des politiques optimales prescrites et des bornes de valeur et permet des méthodes algorithmiques de résolution ; mal appliqué, il produit des politiques peu performantes ou dangereuses en déploiement parce que des dépendances non modélisées ou l’incertitude du modèle annulent l’optimalité.

Inversion

Si l’agent n’observe pas l’état complet, le problème est un POMDP et exige une augmentation de l’état par la croyance ; si les probabilités de transition ou les récompenses sont inconnues, il faut recourir à l’apprentissage par renforcement ou à des MDP robustes ; des espaces d’état/action continus ou très grands nécessitent une approximation par fonctions, une décomposition hiérarchique ou des algorithmes approximatifs qui abandonnent la solution exacte de Bellman.

Limite

Clairement inclus — problèmes discrets à états/actions finis avec probabilités de transition et récompenses connues et traitables par programmation dynamique. Cas limite — espaces d’états/actions volumineux ou continus où la DP exacte est infaisable et requiert approximation. Clairement exclu — contextes adversariaux sans modèle stochastique de transition (formulations de théorie des jeux) ou décisions ponctuelles sans structure séquentielle.

Tension sémantique

Arbitrage entre fidélité du modèle et tractabilité computationnelle : représenter toute l’information pertinente dans l’état garantit la structure markovienne mais augmente la dimension et le coût de calcul; simplifier l’état rend le calcul faisable mais viole la Markovité et dégrade la qualité de la politique.

Synthèse

Les MDP formalisent la prise de décision séquentielle stochastique et mettent en lumière la récurrence de Bellman comme principe central; leur efficacité pratique dépend de la pertinence de la représentation d’état et de la possibilité d’obtenir ou d’apprendre les modèles de transition/récompense avec les ressources disponibles.