Un Proceso de Decisión Markoviano tiene que ver con ir de un estado a otro y se utiliza principalmente para planificar y tomar decisiones.
La teoría
Simplemente repitiendo rápidamente la teoría, un MDP es:
$$\text{MDP} = \langle S,A,T,R,\gamma \rangle$$
donde $S$ son los estados, $A$ las acciones, $T$ las probabilidades de transición (es decir, las probabilidades $Pr(s'|s, a)$ de ir de un estado a otro dado una acción), $R$ las recompensas (dado un cierto estado, y posiblemente acción), y $\gamma$ es un factor de descuento que se utiliza para reducir la importancia de las recompensas futuras.
Por lo tanto, para utilizarlo, necesitas tener predefinido:
- Estados: estos pueden referirse por ejemplo a mapas de cuadrícula en robótica, o por ejemplo puerta abierta y puerta cerrada.
- Acciones: un conjunto fijo de acciones, como por ejemplo ir al norte, sur, este, etc. para un robot, o abrir y cerrar una puerta.
- Probabilidades de transición: la probabilidad de ir de un estado a otro dado una acción. Por ejemplo, ¿cuál es la probabilidad de una puerta abierta si la acción es abrir? En un mundo perfecto esto último podría ser 1.0, pero si se trata de un robot, podría haber fallado en manejar correctamente el picaporte. Otro ejemplo en el caso de un robot en movimiento sería la acción norte, que en la mayoría de los casos lo llevaría a la celda de la cuadrícula al norte de él, pero en algunos casos podría haberse movido demasiado y haber alcanzado la siguiente celda, por ejemplo.
- Recompensas: estas se utilizan para guiar la planificación. En el ejemplo de la cuadrícula, podríamos querer ir a una celda específica, y la recompensa será mayor si nos acercamos. En el caso del ejemplo de la puerta, una puerta abierta podría dar una alta recompensa.
Una vez que se define el MDP, se puede aprender una política realizando Iteración de Valor o Iteración de Política que calculan la recompensa esperada para cada uno de los estados. La política luego da por estado la acción mejor (dado el modelo MDP) a realizar.
En resumen, un MDP es útil cuando se quiere planificar una secuencia eficiente de acciones en la que tus acciones no siempre son 100% efectivas.
Tus preguntas
¿Se puede usar para predecir cosas?
Yo lo llamaría planificación, no predicción como regresión por ejemplo.
En caso afirmativo, ¿qué tipos de cosas?
Ver ejemplos.
¿Puede encontrar patrones entre cantidades infinitas de datos?
Los MDP se utilizan para hacer Aprendizaje por Refuerzo, para encontrar patrones necesitas Aprendizaje No Supervisado. Y no, no puedes manejar una cantidad infinita de datos. De hecho, la complejidad de encontrar una política crece exponencialmente con el número de estados $|S|$.
¿Qué puede hacer este algoritmo por mí?
Ver ejemplos.
Ejemplos de Aplicaciones de MDPs
- White, D.J. (1993) menciona una larga lista de aplicaciones:
- Cosecha: cuántos miembros de una población deben quedar para la cría.
- Agricultura: cuánto plantar según el clima y el estado del suelo.
- Recursos hídricos: mantener el nivel de agua correcto en embalses.
- Inspección, mantenimiento y reparación: cuándo reemplazar/inspeccionar según la edad, condición, etc.
- Compra y producción: cuánto producir según la demanda.
- Colas: reducir el tiempo de espera.
- ...
- Finanzas: decidir cuánto invertir en acciones.
- Robótica:
Y hay varios modelos más. Un modelo aún más interesante es el Proceso de Decisión Markoviano Parcialmente Observable en el cual los estados no son completamente visibles, y en su lugar, se utilizan observaciones para tener una idea del estado actual, pero esto está fuera del alcance de esta pregunta.
Información Adicional
Un proceso estocástico es Markoviano (o tiene la propiedad de Markov) si la distribución de probabilidad condicional de los estados futuros depende solo del estado actual, y no de los anteriores (es decir, no de una lista de estados anteriores).
