Comencemos dando una definición formal de los MDP:
A Proceso de decisión de Markov es una 5-tupla (S, A, R, P, γ) tal que:
- S es el conjunto de Estados El agente puede estar en
- A es el conjunto de comportamiento El agente puede tomar
- R : S incógnita Un → R el premio función
- P es el conjunto de distribuciones de probabilidad definida de modo que P(s’|s,a) es la probabilidad de transición al estado s’ Si el agente toma acción a En el estado sTenga en cuenta que los MDP son procesos de Markov, lo que significa que la propiedad de Markov se cumple en las probabilidades de transición.: P(Sₜ₊₁|S₀, A₀, …, Sₜ, Aₜ) = P(Sₜ₊₁|Sₜ, Aₜ)
- γ ∈ (0, 1]es un factor de descuentoSi bien normalmente tratamos con problemas descontados (es decir, γ < 1), las formulaciones presentadas también son válidas para MDP no descontados (γ = 1)
A continuación definimos el políticaes decir, lo que dicta el comportamiento del agente en un MDP:
Una política π es una medida de probabilidad sobre el espacio de acción definido como: π(a|s) es la probabilidad de tomar acción a cuando el agente está en estado s.
Finalmente presentamos el función de valores decir, el objetivo del agente en un MDP:
La función de valor de una política π es la recompensa descontada esperada bajo esta política, al comenzar en un estado determinado. s:
En particular, la función de valor de la política óptima π* satisface la ecuación de optimalidad de Bellman:
Lo que produce la política óptima determinista:
Derivación de la formulación LP de MDP:
Dadas las definiciones anteriores, podemos comenzar notando que cualquier función de valor V que satisfaga
es un límite superior de la función de valor óptimo. Para verlo, podemos empezar por notar que dicha función de valor también satisface:
Reconocemos el operador de iteración de valor aplicado a V:
es decir
Observando también que el operador H* es creciente, podemos aplicarlo iterativamente para tener:
donde utilizamos la propiedad de V* siendo el punto fijo de H*.
Por lo tanto, encontrar V* se reduce a encontrar el límite superior más estricto V que obedece la ecuación anteriorlo que da como resultado la siguiente formulación:
Aquí agregamos un término de peso correspondiente a la probabilidad de comenzar en el estado sPodemos ver que el problema anterior es lineal en V y puede reescribirse de la siguiente manera: