Procés de decisió de Màrkov

Exemple d'un MDP simple amb tres estats (cercles verds) i dues accions (cercles taronges), amb dues recompenses (fletxes taronges).

En matemàtiques, un procés de decisió de Màrkov (amb acrònim anglès MDP) és un procés de control estocàstic en temps discret. Proporciona un marc matemàtic per modelar la presa de decisions en situacions en què els resultats són en part aleatoris i en part sota el control d'un decisor. Els MDP són útils per estudiar problemes d'optimització resolts mitjançant programació dinàmica. Els MDP eren coneguts almenys ja als anys 50; Un conjunt bàsic d'investigació sobre els processos de decisió de Màrkov va resultar del llibre de 1960 de Ronald Howard, Programació dinàmica i processos de Màrkov. S'utilitzen en moltes disciplines, com ara la robòtica, el control automàtic, l'economia i la fabricació. El nom de MDP prové del matemàtic rus Andrey Màrkov ja que són una extensió de les cadenes de Màrkov.

En cada pas de temps, el procés es troba en algun estat $s$, i qui pren la decisió pot triar qualsevol acció $a$ que està disponible a l'estat $s$. El procés respon al següent pas passant aleatòriament a un nou estat $s'$, i donar a qui pren la decisió una recompensa corresponent $R_{a}(s,s')$.

La probabilitat que el procés passi al seu nou estat $s'$ està influenciat per l'acció escollida. Concretament, ve donada per la funció de transició d'estats $P_{a}(s,s')$. Així, el següent estat $s'$ depèn de l'estat actual $s$ i l'acció de qui pren la decisió $a$. Però donat $s$ i $a$, és condicionalment independent de tots els estats i accions anteriors; en altres paraules, les transicions d'estat d'un MDP satisfan la propietat de Màrkov.

Els processos de decisió de Màrkov són una extensió de les cadenes de Màrkov; la diferència és l'afegit d'accions (permet triar) i recompenses (donar motivació). Per contra, si només existeix una acció per a cada estat (per exemple, "espera") i totes les recompenses són iguals (per exemple, "zero"), un procés de decisió de Màrkov es redueix a una cadena de Màrkov.

Un procés de decisió de Màrkov és una tupla 4 $(S,A,P_{a},R_{a})$, on:

• és un conjunt d'estats anomenat espai d'estats,
• és un conjunt d'accions anomenat espai d'acció (alternativament, és el conjunt d'accions disponibles per part de l'estat ),
• és la probabilitat que l'acció en estat en el moment portarà a l'estat en el moment ,
• és la recompensa immediata (o la recompensa immediata esperada) rebuda després de la transició de l'estat declarar , a causa de l'acció

Els espais d'estat i d'acció poden ser finits o infinits, per exemple el conjunt de nombres reals. Alguns processos amb espais d'acció i estats infinits es poden reduir a uns amb espais d'acció i estats finits.

Una funció política $\pi$ és un mapeig (potencialment probabilístic) de l'espai d'estats ($S$) a l'espai d'acció ($A$).