Markov Decision Process (MDP)

Detto anche: MDP
Categoria: Learning & autonomy › RL & simulation
Tag: reinforcement-learning, decision-making, dynamic-programming, probability, robot-learning

Il modello matematico standard del processo decisionale sequenziale: stati, azioni, probabilità di transizione, ricompense e un fattore di sconto, con lo stato successivo che dipende solo dallo stato e dall'azione correnti.

Definizione

Un processo decisionale di Markov (Markov decision process, MDP) descrive un agente che ripetutamente osserva uno stato, sceglie un'azione, riceve una ricompensa e passa a un nuovo stato. Di solito si scrive come una tupla (S, A, P, R, γ), spesso con una distribuzione dello stato iniziale ρ₀: lo spazio degli stati, lo spazio delle azioni, le probabilità di transizione P(s′ | s, a), la funzione di ricompensa R(s, a) e un fattore di sconto γ compreso tra 0 e 1 che pesa le ricompense future rispetto a quelle immediate. L'ipotesi che lo definisce è la proprietà di Markov: la distribuzione dello stato successivo dipende solo dallo stato e dall'azione correnti, non dalla storia che vi ha condotto. Il lavoro di Richard Bellman sulla programmazione dinamica negli anni 1950 ha fondato il quadro teorico.

L'obiettivo in un MDP è una policy, una funzione dagli stati alle azioni (o a distribuzioni sulle azioni), che massimizzi la somma scontata attesa delle ricompense. La funzione di valore V(s) e la funzione di valore azione Q(s, a) danno questo ritorno atteso a partire da uno stato, o da uno stato e un'azione, sotto una policy. Esse soddisfano le equazioni di Bellman, che esprimono il valore di uno stato come la ricompensa immediata più il valore scontato degli stati che seguono. Quando P e R sono note e lo spazio degli stati è piccolo, l'iterazione dei valori e l'iterazione della policy risolvono l'MDP in modo esatto. Quando sono ignote, o gli spazi sono grandi e continui, l'apprendimento per rinforzo stima valori e policy a partire da esperienza campionata.

Gli MDP sono la base formale di quasi tutto l'apprendimento per rinforzo e di gran parte della pianificazione in condizioni di incertezza. Molte varianti rilassano una delle ipotesi: un MDP parzialmente osservabile (POMDP) abbandona l'ipotesi che l'agente veda lo stato vero; gli MDP vincolati aggiungono limiti di costo; i semi-MDP ammettono azioni di durata variabile; ed estensioni multi-agente come i giochi di Markov modellano più decisori. Scegliere che cosa entra nello stato è una decisione ingegneristica: se si tralasciano informazioni importanti come velocità, stato di contatto o intenzione degli altri agenti, il processo non è più markoviano dal punto di vista dell'agente.

Perché è importante

Ogni articolo di apprendimento per rinforzo e la maggior parte dei metodi decisionali in robotica formulano il proprio problema come un MDP o una sua variante. Conoscere le parti della tupla, e su quale ipotesi si basa ciascun metodo, permette di leggere quegli articoli, progettare stati e ricompense per un robot reale e riconoscere quando un problema è in realtà parzialmente osservabile.

Applicazioni principali

Formulazione di problemi di apprendimento per rinforzo per manipolazione e locomozione
Pianificazione in condizioni di incertezza con iterazione dei valori e iterazione della policy
Progettazione delle ricompense e apprendimento per rinforzo inverso, che inferiscono o modellano R
Apprendimento per rinforzo basato su modello, che apprende la funzione di transizione P
Modellazione dell'interazione con altri agenti tramite giochi di Markov e variabili latenti di intenzione

In pratica

Un gruppo che addestra un braccio robotico a spingere un blocco verso un bersaglio formula il compito come un MDP. Lo stato contiene gli angoli e le velocità dei giunti, la posa del blocco e la posizione del bersaglio; l'azione è una variazione della posizione dell'end effector a ogni passo di controllo; la ricompensa è la distanza negativa tra blocco e bersaglio con un bonus in caso di successo; e γ è impostato vicino a 1 perché il compito si estende su molti passi. Nei primi test la policy si comporta in modo irregolare quando il blocco è in movimento, perché lo stato include la posa del blocco ma non la sua velocità. Aggiungere la velocità del blocco, o impilare le ultime osservazioni, ripristina la proprietà di Markov in modo abbastanza fedele perché un algoritmo standard come SAC o PPO apprenda in modo affidabile.

Idee sbagliate comuni

Un MDP richiede stati e azioni discreti — gli spazi degli stati e delle azioni continui sono comuni in robotica, con le somme sostituite da integrali e i metodi tabellari sostituiti dall'approssimazione di funzioni
La proprietà di Markov è un fatto del mondo — è una proprietà dello stato scelto; tralasciare velocità o variabili nascoste può rendere un sistema fisico non markoviano dal punto di vista dell'agente
Il fattore di sconto riflette solo l'impazienza — limita anche il ritorno nei problemi a orizzonte infinito e influisce sulla varianza e sulla stabilità dell'apprendimento, per cui spesso viene regolato come un iperparametro
Risolvere un MDP richiede un modello di P — i metodi di apprendimento per rinforzo trovano buone policy a partire da transizioni campionate senza mai scrivere P

Chi dovrebbe saperlo

Professionisti e ricercatori dell'apprendimento per rinforzo
Ingegneri di apprendimento robotico che progettano stati, azioni e ricompense
Ricercatori di pianificazione e processi decisionali
Studenti di robotica che iniziano con l'apprendimento robotico

Tecnologie correlate

Equazione di Bellman (Bellman Equation)
Iterazione dei valori (Value Iteration)
Iterazione della policy (Policy Iteration)
Q-Learning
Gymnasium
Programmazione dinamica (Dynamic Programming)

Termini correlati

Progetti correlati

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

Video

Markov Decision Processes - Computerphile: Computerphile