Tema

Trazas de elegibilidad

• Aprendizaje por refuerzo
• Nivel avanzado

Las trazas de elegibilidad guardan una huella que decae de los estados visitados hace poco y reparten cada error temporal entre todos ellos, lo que interpola entre el método de un paso y Monte Carlo.

Nombre en inglés

Eligibility traces

Intuición

Cuando llega una sorpresa, no solo tuvo la culpa el último estado sino también los que llevaron hasta él, y la traza mide cuánta responsabilidad le toca a cada uno. El parámetro lambda gradúa esa memoria, ya que con lambda igual a cero se recupera el método de un paso y con lambda igual a uno se recupera Monte Carlo en su forma incremental. La ventaja práctica es que la información viaja muchos estados hacia atrás en un solo episodio en lugar de uno por episodio.

Fórmula

e_t(s) = \gamma \lambda e_{t-1}(s) + [S_t = s] \qquad V(s) \leftarrow V(s) + \alpha \delta_t e_t(s)

Ejemplo resuelto

Se retoma el episodio que visita A, después B y termina, con recompensas 0 y 1, descuento 1, tasa 0.5 y lambda 0.5. Tras el primer paso, la traza de A vale 1 y el error vale 0, de modo que nada cambia. En el segundo paso, la traza de A decae a 1 por 0.5 = 0.5 y la de B vale 1, mientras que el error vale 1. La actualización deja B en 0.5 por 1 por 1 = 0.5 y A en 0.5 por 1 por 0.5 = 0.25. Conviene comparar con el método de un paso, que en ese mismo episodio dejó A en 0, y con Monte Carlo, que lo habría dejado en 0.5.

Errores frecuentes

• Acumular la traza sin cota en estados que se repiten mucho, lo que puede desestabilizar la actualización; la traza de reemplazo la fija en 1 cada vez que se visita el estado.
• Confundir lambda con el descuento, cuando el descuento rebaja el futuro y lambda reparte la culpa hacia el pasado.
• Mantener las trazas entre episodios, ya que al empezar uno nuevo deben ponerse todas a cero.

Ejercicio

Con un descuento de 0.9 y lambda 0.5, un estado se visita y después pasan tres pasos sin volver a visitarlo. ¿Cuánto vale su traza?

Temas relacionados

• Aprendizaje por diferencias temporales
• Métodos de Monte Carlo
• SARSA y aprendizaje dentro de política
• Aproximación de funciones

Cursos a los que prepara

• CS 7642 Reinforcement Learning and Decision Making