Tema

Procesos de decisión de Markov

• Machine Learning
• Nivel avanzado

Un proceso de decisión de Markov describe un problema secuencial con estados, acciones, una función de transición estocástica, una recompensa y un factor de descuento, y su solución es una política que maximiza la recompensa acumulada esperada.

Nombre en inglés

Markov decision processes

Intuición

Es el puente entre el aprendizaje supervisado y el aprendizaje por refuerzo, porque la etiqueta deja de venir dada y se sustituye por una recompensa que llega tarde y repartida. La propiedad de Markov promete que el estado actual resume todo lo que importa del pasado, de modo que la política puede depender solo del estado. El factor de descuento hace finita la suma de recompensas y expresa cuánto vale menos un premio lejano que uno inmediato.

Fórmula

V*(s) = max_a [ R(s, a) + gamma * sum_{s'} P(s' | s, a) V*(s') ],  con 0 <= gamma < 1

Ejemplo resuelto

Hay dos estados, A y B, y el descuento vale 0.9. En A caben dos acciones, quedarse, que da recompensa 1 y deja el estado en A, o saltar, que da recompensa 0 y lleva a B. En B solo cabe una acción, que da recompensa 5 y mantiene el estado. Partiendo de valores nulos, la primera pasada da V(A) = 1 y V(B) = 5. La segunda da V(A) = max(1 + 0.9 por 1, 0 + 0.9 por 5) = max(1.9, 4.5) = 4.5 y V(B) = 5 + 0.9 por 5 = 9.5. La política preferida en A cambia de quedarse a saltar en cuanto el algoritmo ve más allá de un paso.

Errores frecuentes

• Fijar el factor de descuento en 1 sin estados terminales, con lo que la suma de recompensas diverge y la comparación entre políticas pierde sentido.
• Confundir la función de valor con la política, ya que el valor es un número por estado y la política es la acción elegida en cada estado, aunque una se derive de la otra.
• Dar recompensa por estar en un estado bueno en lugar de por la transición que lleva a él, error de diseño que crea bucles donde el agente cobra sin avanzar.

Ejercicio

Con el proceso del ejemplo y los valores V(A) = 4.5 y V(B) = 9.5, calcula la siguiente iteración de V(A).

Temas relacionados

• Iteración de valor
• Ecuaciones de Bellman
• Q-learning
• Agentes y entornos
• Redes neuronales básicas

Cursos a los que prepara

• CS 7641 Machine Learning
• CS 7642 Reinforcement Learning and Decision Making
• CS 6601 Artificial Intelligence