Tema

Métodos de Monte Carlo

• Aprendizaje por refuerzo
• Nivel intermedio

Los métodos de Monte Carlo estiman el valor de un estado promediando los retornos observados en episodios completos, sin modelo de transiciones y sin apoyarse en estimaciones de otros estados.

Nombre en inglés

Monte Carlo methods

Intuición

Si no se conoce el modelo, se juega la partida hasta el final y se anota lo que se cobró, de manera que con muchas partidas el promedio se acerca al valor verdadero. La estimación no arrastra el error de otros estados, motivo por el cual carece de sesgo, pero depende de todo lo ocurrido después y por eso su varianza resulta alta. La condición práctica es que la tarea termine, ya que sin final no hay retorno que promediar.

Fórmula

V(s) \leftarrow V(s) + \alpha [G_t - V(s)] \qquad G_t = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{T-t-1} R_T

Ejemplo resuelto

Un episodio visita A, después B y termina, con recompensa 0 al salir de A y 1 al salir de B, y descuento 0.9. El retorno desde B vale 1 y el retorno desde A vale 0 más 0.9 por 1 = 0.9. Con todos los valores en cero y una tasa de 0.5, la actualización deja A en 0.5 por 0.9 = 0.45 y B en 0.5. Un segundo episodio idéntico deja A en 0.45 más 0.5 por (0.9 menos 0.45) = 0.675 y B en 0.75. Con promedio corriente en vez de tasa fija, dos episodios darían directamente 0.9 y 1, que son los valores verdaderos de esta cadena determinista.

Errores frecuentes

• Actualizar a mitad de episodio, cuando el retorno solo se conoce al llegar al final.
• Mezclar la variante de primera visita con la de todas las visitas dentro del mismo cálculo, ya que promedian conjuntos distintos aunque ambas converjan.
• Aplicar Monte Carlo a una tarea continua, que no produce retornos completos y obliga a cortar el episodio de forma artificial.

Ejercicio

Un episodio entrega las recompensas 1, 0 y 2 y termina, con un descuento de 0.5. ¿Cuál es el retorno desde el primer paso?

Temas relacionados

• Aprendizaje por diferencias temporales
• Trazas de elegibilidad
• Procesos de decisión de Markov
• Esperanza y varianza

Cursos a los que prepara

• CS 7642 Reinforcement Learning and Decision Making