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.

Definició

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

• $S$ és un conjunt d'estats anomenat espai d'estats,
• $A$ és un conjunt d'accions anomenat espai d'acció (alternativament, és el conjunt d'accions disponibles per part de l'estat ),
• $P_{a}$és la probabilitat que l'acció en estat en el moment portarà a l'estat en el moment ,
• $R_{a}$ é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$).

En el context del procés de presa de decisions de Markov (MDP) és un mapeig que associa els estats possibles ($S$) amb les accions possibles ($A$). És una funció que determina quina acció ha de prendre's en cada estat en funció dels objectius i les recompenses esperades. La funció política pot ser determinista o probabilística, depenent del tipus de MDP:

• En un MDP determinista, la funció política determinista assigna una única acció a cada estat. Per exemple, si tenim un MDP que representa un joc de taula, la funció política determinista podria indicar quina moviment fer en cada posició del tauler.
• En un MDP probabilístic, la funció política probabilística assigna una distribució de probabilitat a les accions en cada estat. Això significa que en un mateix estat, l'agent pot prendre diferents accions amb probabilitats diferents. Aquesta flexibilitat permet tenir en compte la incertesa o el risc associat a les diferents accions.

L'objectiu de la funció política és maximitzar una funció d'utilitat o recompensa esperada. En un MDP, les accions d'un agent afecten l'estat actual i l'estat següent, juntament amb una recompensa associada a aquesta transició. L'agent busca trobar la millor seqüència d'accions per maximitzar la seva recompensa acumulada al llarg del temps.

Hi ha diferents mètodes per trobar la funció política òptima. Un dels mètodes més comuns és l'algorisme de valor iteratiu, com l'algorisme de valor de Bellman o l'algorisme Q-learning. Aquests mètodes exploren i actualitzen iterativament els valors de la funció d'utilitat o recompensa esperada per determinar la millor política.

En resum, la funció política en un MDP és un mapeig que associa els estats possibles amb les accions possibles, determinant quina acció prendre en cada estat per maximitzar la recompensa esperada. Pot ser determinista o probabilística, i l'objectiu és trobar la millor política per optimitzar els resultats en un MDP.