Markov Decision Process (MDP)

Aussi appelé: MDP
Catégorie: Learning & autonomy › RL & simulation
Mots-clés: reinforcement-learning, decision-making, dynamic-programming, probability, robot-learning

Le modèle mathématique standard de la prise de décision séquentielle : états, actions, probabilités de transition, récompenses et facteur d'actualisation, l'état suivant ne dépendant que de l'état et de l'action courants.

Définition

Un processus de décision markovien (Markov decision process, MDP) décrit un agent qui, de manière répétée, observe un état, choisit une action, reçoit une récompense et passe à un nouvel état. On l'écrit généralement comme un tuple (S, A, P, R, γ), souvent accompagné d'une distribution d'état initial ρ₀ : l'espace d'états, l'espace d'actions, les probabilités de transition P(s′ | s, a), la fonction de récompense R(s, a) et un facteur d'actualisation γ compris entre 0 et 1, qui pondère les récompenses futures par rapport aux récompenses immédiates. L'hypothèse qui le définit est la propriété de Markov : la distribution de l'état suivant ne dépend que de l'état et de l'action courants, et non de l'historique qui y a conduit. Les travaux de Richard Bellman sur la programmation dynamique dans les années 1950 ont établi ce cadre.

Le but dans un MDP est une politique, c'est-à-dire une application des états vers les actions (ou vers des distributions sur les actions), qui maximise l'espérance de la somme actualisée des récompenses. La fonction de valeur V(s) et la fonction de valeur action-état Q(s, a) donnent ce retour espéré à partir d'un état, ou d'un état et d'une action, sous une politique donnée. Elles satisfont les équations de Bellman, qui expriment la valeur d'un état comme la récompense immédiate plus la valeur actualisée des états qui suivent. Lorsque P et R sont connus et que l'espace d'états est petit, l'itération sur les valeurs et l'itération sur les politiques résolvent le MDP exactement. Lorsqu'ils sont inconnus, ou que les espaces sont grands et continus, l'apprentissage par renforcement estime valeurs et politiques à partir d'expérience échantillonnée.

Les MDP sont le fondement formel de presque tout l'apprentissage par renforcement et d'une grande part de la planification sous incertitude. De nombreuses variantes relâchent l'une des hypothèses : un MDP partiellement observable (POMDP) abandonne l'hypothèse selon laquelle l'agent voit l'état réel ; les MDP contraints ajoutent des limites de coût ; les semi-MDP autorisent des actions de durée variable ; et les extensions multi-agents comme les jeux de Markov modélisent plusieurs décideurs. Le choix de ce qui entre dans l'état est une décision d'ingénierie : si des informations importantes comme les vitesses, l'état de contact ou l'intention des autres agents en sont exclues, le processus n'est plus markovien du point de vue de l'agent.

Pourquoi c'est important

Tous les articles d'apprentissage par renforcement et la plupart des méthodes de prise de décision en robotique formulent leur problème comme un MDP ou une de ses variantes. Connaître les éléments du tuple, et l'hypothèse sur laquelle repose chaque méthode, permet de lire ces articles, de concevoir des états et des récompenses pour un robot réel et de reconnaître quand un problème est en réalité partiellement observable.

Applications principales

Formulation de problèmes d'apprentissage par renforcement pour la manipulation et la locomotion
Planification sous incertitude par itération sur les valeurs et itération sur les politiques
Conception de récompenses et apprentissage par renforcement inverse, qui infèrent ou façonnent R
Apprentissage par renforcement fondé sur un modèle, qui apprend la fonction de transition P
Modélisation de l'interaction avec d'autres agents par des jeux de Markov et des variables d'intention latentes

En pratique

Une équipe qui entraîne un bras robotique à pousser un bloc jusqu'à une cible formule la tâche comme un MDP. L'état contient les angles et vitesses articulaires, la pose du bloc et la position de la cible ; l'action est une variation de la position de l'effecteur terminal à chaque pas de commande ; la récompense est l'opposé de la distance entre le bloc et la cible, avec un bonus en cas de succès ; et γ est fixé près de 1 parce que la tâche s'étend sur de nombreux pas. Lors des premiers essais, la politique se comporte de façon erratique quand le bloc est en mouvement, parce que l'état inclut la pose du bloc mais pas sa vitesse. Ajouter la vitesse du bloc, ou empiler les dernières observations, rétablit la propriété de Markov assez fidèlement pour qu'un algorithme standard comme SAC ou PPO apprenne de façon fiable.

Idées reçues

Un MDP exige des états et des actions discrets — les espaces d'états et d'actions continus sont courants en robotique, les sommes étant remplacées par des intégrales et les méthodes tabulaires par l'approximation de fonctions
La propriété de Markov est un fait concernant le monde — c'est une propriété de l'état choisi ; omettre les vitesses ou des variables cachées peut rendre un système physique non markovien du point de vue de l'agent
Le facteur d'actualisation ne traduit que l'impatience — il borne aussi le retour dans les problèmes à horizon infini et influe sur la variance et la stabilité de l'apprentissage, si bien qu'on le règle souvent comme un hyperparamètre
Résoudre un MDP nécessite un modèle de P — les méthodes d'apprentissage par renforcement trouvent de bonnes politiques à partir de transitions échantillonnées sans jamais écrire P

Qui devrait le savoir

Praticiens et chercheurs en apprentissage par renforcement
Ingénieurs en apprentissage robotique qui conçoivent états, actions et récompenses
Chercheurs en planification et en prise de décision
Étudiants en robotique qui débutent en apprentissage robotique

Technologies associées

Équation de Bellman (Bellman Equation)
Itération sur les valeurs (Value Iteration)
Itération sur les politiques (Policy Iteration)
Q-Learning
Gymnasium
Programmation dynamique (Dynamic Programming)

Termes associés

Projets associés

LeRobot: HuggingFace ML library for real-world robotics in PyTorch
MuJoCo: DeepMind physics engine for robotics and ML research
PyBullet: Python physics simulator for robotics and RL research with fast CPU-based simulation
OpenPI: Physical Intelligence VLA foundation models for general robot control
Microduck: Pollen Robotics' $399 walking duck robot: open-source software, closed hardware
Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim

Vidéos

Markov Decision Processes - Computerphile: Computerphile