Tema
Procesos de decisión de Markov
- Aprendizaje por refuerzo
- Nivel base
Un proceso de decisión de Markov describe un problema de decisión secuencial mediante estados, acciones, probabilidades de transición, recompensas y un factor de descuento, bajo el supuesto de que el estado actual resume toda la historia relevante.
Nombre en inglés
Markov decision processes
Intuición
La propiedad de Markov es la que vuelve tratable el problema, porque permite decidir mirando solo dónde se está y no cómo se llegó. El factor de descuento pone precio al tiempo, ya que una recompensa dentro de diez pasos vale menos que la misma recompensa ahora, y además garantiza que la suma resulte finita en tareas sin final. Elegir bien el estado es la mitad del trabajo, puesto que un estado incompleto rompe la propiedad y arruina cualquier algoritmo posterior.
Fórmula
M = (S, A, P, R, \gamma) \qquad G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \qquad 0 \le \gamma < 1
Ejemplo resuelto
Un episodio entrega las recompensas 0, 0 y 1 en tres pasos y termina. Con un descuento de 0.9, el retorno desde el tercer paso vale 1, desde el segundo vale 0 más 0.9 por 1 = 0.9 y desde el primero vale 0 más 0.9 por 0.9 = 0.81. Con un descuento de 0.5 los mismos premios valen 1, 0.5 y 0.25, es decir, el agente se vuelve mucho más impaciente. Si en cambio la tarea no terminase y entregase 1 en cada paso, el retorno con descuento 0.9 valdría 1 dividido entre 1 menos 0.9, es decir, 10, mientras que con descuento 1 sería infinito y la comparación entre políticas dejaría de tener sentido.
Errores frecuentes
- Incluir en el estado menos información de la necesaria, con lo que dos situaciones distintas comparten estado y la propiedad de Markov se rompe.
- Confundir la recompensa con el retorno, cuando la primera es el premio inmediato y el segundo es la suma descontada de todos los futuros.
- Usar un descuento de 1 en una tarea sin final, lo que hace divergir el retorno y deja sin definir la comparación entre políticas.
Ejercicio
Un agente recibe una recompensa de 2 en cada paso durante infinitos pasos, con un descuento de 0.8. ¿Cuánto vale el retorno?
Ver la solución
La suma es 2 multiplicado por la serie geométrica de razón 0.8, cuya suma vale 1 dividido entre 1 menos 0.8, es decir, 5. El retorno es 2 por 5 = 10.
Respuesta: 10