Markov Decision Process (MDP)

Un processus décisionnel de Markov (MDP) est le modèle mathématique d’un problème de décision séquentiel : un agent observe un état, choisit une action, reçoit une récompense et aboutit à un nouvel état qui dépend en partie de son choix et en partie du hasard. Formellement, un MDP comprend un ensemble d’états, un ensemble d’actions, des probabilités de transition P(s′ | s, a), une fonction de récompense R(s, a) et, généralement, un facteur d’actualisation γ compris entre 0 et 1. Le résoudre revient à trouver une politique — une règle qui choisit une action dans chaque état — qui maximise la somme actualisée espérée des récompenses futures. Les MDP sont issus de la recherche opérationnelle des années 1950, où la programmation dynamique de Richard Bellman a fourni les méthodes nécessaires à leur résolution ; ils constituent la formulation standard des problèmes d’apprentissage par renforcement (RL).

La propriété de Markov#

L’hypothèse fondamentale est la propriété de Markov : le nouvel état et la récompense dépendent uniquement de l’état et de l’action actuels, et non du parcours qui y a mené. L’état résume donc tout ce qui est pertinent pour l’agent. Une seule image de caméra ne respecte pas cette hypothèse pour un objet en mouvement, car elle montre sa position, mais pas sa vitesse ; c’est pourquoi le DQN de DeepMind qui jouait à l’Atari fournissait à son réseau les quatre dernières images empilées, afin de lui permettre de voir le mouvement.

Lorsque l’agent ne peut pas observer l’état complet, comme dans le cas d’un robot dont les capteurs sont bruités ou occultés, le problème est un MDP partiellement observable (POMDP). L’agent agit alors en fonction d’une croyance sur l’état, maintenue par un filtre ou un réseau récurrent, plutôt qu’en fonction de l’état lui-même.

Composants d’un MDP#

• États : les situations dans lesquelles l’agent peut se trouver, comme les angles des articulations d’un robot et la position de l’objet qu’il essaie d’atteindre.
• Actions : les choix possibles dans chaque état. L’espace d’actions peut être discret (tourner à gauche, tourner à droite) ou continu (un angle de braquage en degrés).
• Probabilités de transition : la probabilité de chaque nouvel état après une action, qui prend en compte le patinage des roues, les autres conducteurs et toute autre source d’aléatoire.
• Récompenses : le retour numérique immédiat associé à une transition. Le choix des récompenses par le concepteur définit la tâche, et un choix imprudent peut entraîner du piratage des récompenses.
• Facteur d’actualisation : l’importance des récompenses futures par rapport aux récompenses immédiates. Avec γ = 0.9, une récompense obtenue dans dix étapes vaut 0.9¹⁰ ≈ 0.35 fois la même récompense obtenue maintenant.

À chaque pas de temps, la même interaction se répète jusqu’à la fin de l’épisode :

Résoudre un MDP#

La valeur d’un état correspond au rendement espéré à partir de cet état, selon une politique donnée, et les valeurs optimales satisfont l’équation de Bellman : la valeur de chaque état est égale à la récompense immédiate de la meilleure action, à laquelle s’ajoute la valeur actualisée et pondérée par les probabilités des états auxquels elle mène. Lorsque les probabilités de transition et les récompenses sont connues, la programmation dynamique résout directement cette équation. L’itération sur les valeurs (Bellman, 1957) l’applique à plusieurs reprises jusqu’à ce que les valeurs cessent de changer, tandis que l’itération sur les politiques (Howard, 1960) alterne entre l’évaluation d’une politique et son amélioration.

Cet exemple NumPy applique l’itération sur les valeurs au robot recycleur de Reinforcement Learning: An Introduction, de Sutton et Barto ; ce robot doit choisir entre chercher des canettes, attendre et recharger sa batterie, qu’elle soit haute ou faible :

import numpy as np

# MDP du robot recycleur : états 0 = batterie haute, 1 = batterie faible ; actions 0 = chercher, 1 = attendre, 2 = recharger
gamma = 0.9  # facteur d’actualisation
P = np.zeros((2, 3, 2))  # P[s, a, s'] = probabilité d’atteindre s' après avoir choisi a dans l’état s
P[0, 0] = [0.7, 0.3]  # chercher avec une batterie haute peut la faire passer à un niveau bas
P[1, 0] = [0.4, 0.6]  # chercher avec une batterie faible peut la décharger complètement (le robot est récupéré et rechargé)
P[:, 1] = np.eye(2)  # attendre conserve le niveau de la batterie
P[:, 2] = [1.0, 0.0]  # recharger rétablit toujours un niveau de batterie élevé
R = np.array([[2.0, 1.0, 0.0], [0.0, 1.0, 0.0]])  # espérance R[s, a] ; recherche avec batterie faible : 0.6 * 2 + 0.4 * -3 = 0

# Itération sur les valeurs : appliquer la mise à jour d’optimalité de Bellman jusqu’à ce que les valeurs cessent de changer
V = np.zeros(2)
for _ in range(500):
    Q = R + gamma * P @ V  # valeur de chaque action dans chaque état
    V = Q.max(axis=1)

actions = ["search", "wait", "recharge"]
print("Optimal values:", V.round(2))
print("Optimal policy:", {s: actions[a] for s, a in zip(["high", "low"], Q.argmax(axis=1))})

Le programme affiche des valeurs de 15.75 pour une batterie haute et de 14.17 pour une batterie faible, ainsi qu’une politique qui consiste à chercher lorsque la batterie est haute et à la recharger lorsqu’elle est faible : le risque de 40 % d’une pénalité de −3 pour récupération rend la recherche avec une batterie faible moins intéressante que la recharge.

Lorsque les probabilités de transition sont inconnues, l’apprentissage par renforcement estime les mêmes valeurs à partir de l’expérience. L’apprentissage Q met à jour les valeurs des actions à partir de transitions échantillonnées, les méthodes de gradient de politique ajustent directement une politique, et l’apprentissage profond par renforcement utilise des réseaux neuronaux lorsque l’espace des états est trop vaste pour être énuméré. Les algorithmes de planification comme la recherche arborescente Monte-Carlo résolvent en ligne d’immenses MDP en simulant uniquement les avenirs accessibles depuis l’état actuel.

MDP et modèles connexes#

• Chaîne de Markov : une suite d’états aléatoires sans actions ni récompenses. Un MDP ajoute les choix et l’objectif.
• Modèle de Markov caché (HMM) : une chaîne de Markov dont les états ne sont observés qu’à travers des signaux bruités. Un POMDP entretient la même relation avec un MDP.
• Bandit à plusieurs bras : un MDP à état unique, où chaque action produit un gain indépendamment du passé.
• Apprentissage par renforcement : la famille de méthodes qui apprennent à agir efficacement dans un MDP par interaction, sans connaître les probabilités de transition.

Applications#

• Robotique et commande : la préhension, la marche et la navigation se formulent comme des MDP, et leurs politiques sont souvent entraînées en simulation. Dans la commande fondée sur des images de caméra, un détecteur comme Ultralytics YOLO26 peut fournir l’état sous la forme d’une courte liste de classes d’objets et de coordonnées de boîtes pour chaque image, une entrée bien plus petite pour la politique que les pixels bruts.
• Entraînement des modèles de langage : le RLHF et le RLVR traitent la génération de texte comme un MDP dont l’état correspond à l’invite et aux jetons générés jusque-là, dont l’action est le jeton suivant et dont la récompense est reçue une fois la réponse terminée.
• Recherche opérationnelle : le réapprovisionnement des stocks, la maintenance des équipements et la tarification dynamique sont des exemples classiques de MDP ; Ronald Howard a mis au point l’itération sur les politiques en optimisant les envois de catalogues de Sears.