Predicción TD y Sarsa

1Aprender del paso siguiente

Monte Carlo con α constante mueve la estimación de cada estado visitado hacia el retorno que vino después:

pero G_t se conoce solo cuando termina el episodio. El método TD más simple, TD(0) o TD de un paso, usa en cambio la recompensa R_t+1 y la estimación del estado siguiente, ambas disponibles en el tiempo t + 1:

¿Por qué es un objetivo razonable? El retorno de un paso es la recompensa siguiente más el retorno descontado del paso siguiente, G_t = R_t+1 + γG_t+1, así que el valor de un estado se puede escribir de dos maneras:

Los tres métodos usan las dos formas de manera distinta:

TD hace ambas cosas a la vez: como la programación dinámica, hace bootstrapping, y como Monte Carlo, no necesita modelo.

El algoritmo

TD(0) tabular, para una política π y un tamaño de paso α en (0, 1]:

1. Parte con cualquier V(s), salvo V(terminal) = 0.
2. Al comienzo de cada episodio, observa el primer estado S.
3. Toma la acción que π da para S, y observa la recompensa R y el estado siguiente S′.
4. Actualiza V(S) ← V(S) + α[R + γV(S′) − V(S)].
5. Haz S ← S′, y vuelve al paso 3 hasta que S sea terminal.

La figura ejecuta TD(0) sobre los mismos 30 episodios de la primera figura del apunte anterior: los movimientos al azar son los mismos, y solo cambia el aprendizaje. Otra vez γ = 0.9, con α = 0.5 y todas las estimaciones partiendo en 0. Ahora a cada movimiento le siguen su TD error, cuyo objetivo usa la estimación con borde rojo, y la actualización.

2Un viaje, paso a paso

Supón que las estimaciones del robot son V(cocina) = −5, V(pasillo) = −4 y V(estudio) = −2, promedios de dos viajes con suerte; los valores reales de su andar al azar son −9, −8 y −5. Su siguiente viaje va cocina, pasillo, cocina, pasillo, estudio, cargador. Con γ = 1 y α = 0.5, TD(0) hace una actualización por movimiento:

En t = 1, volver a la cocina le dice al robot que el pasillo era peor de lo que creía, y TD baja la estimación del pasillo en el acto. En t = 3 el robot llega al estudio desde el pasillo, que es una mejor noticia, y la estimación vuelve a subir. Monte Carlo con α constante espera hasta el cargador, y luego mueve la estimación de cada visita hacia su retorno:

El error de Monte Carlo como suma de TD errors

Si la tabla no cambia durante el episodio, el error de la actualización Monte Carlo es la suma descontada de los TD errors del resto del episodio, porque las estimaciones intermedias se cancelan de a pares:

Con la tabla fija en −5, −4 y −2, los TD errors de este viaje son 0, −2, 0, 1 y 1, que suman 0: exactamente G₀ − V(cocina) = −5 − (−5). TD(0) cambia la tabla sobre la marcha, así que entonces la identidad se cumple solo en forma aproximada; el tercer TD error de arriba es −1 en vez de 0 porque el pasillo ya se había actualizado.

3¿Por qué aprender de una conjetura?

Comparado con la programación dinámica, TD no necesita modelo: ni probabilidades de recompensas y estados siguientes, solo experiencia. Comparado con Monte Carlo, aprende en línea, un paso a la vez. Eso importa:

• cuando los episodios son largos;
• cuando la tarea nunca termina;
• cuando algunas políticas harían que un episodio durara para siempre: Monte Carlo no puede aprender nada de un episodio que nunca termina, mientras que TD se da cuenta durante el episodio de que las cosas van mal.

Además es correcto. Para una política fija π, TD(0) converge a v_π. Lo hace en promedio con un α constante lo bastante pequeño, y con probabilidad 1 si α se achica de la forma habitual, con una suma que crece sin límite y una suma de cuadrados que se mantiene finita. Qué método aprende más rápido no se ha demostrado en general, pero en la práctica TD suele ganarle a Monte Carlo con α constante en tareas con azar.

4Actualización por lotes: a qué converge cada método

Con una cantidad fija de experiencia, digamos unos pocos episodios, se puede repasar una y otra vez hasta que las estimaciones dejen de cambiar. En la actualización por lotes (batch updating), se calculan y suman los incrementos de cada paso de cada episodio, la tabla cambia una sola vez por su suma, y se vuelve a procesar todo el lote, hasta que converge.

Con un α lo bastante pequeño, TD(0) por lotes converge a una única respuesta que no depende de α, y lo mismo Monte Carlo por lotes, pero las dos respuestas son distintas.

Un ejemplo. A veces otro robot ocupa el cargador. Llegar a él desde el estudio da +1 si está libre y 0 si está ocupado, y moverse del pasillo al estudio da −1; γ = 1. Se registraron cinco episodios:

Ambos métodos le dan al estudio el promedio de sus cinco retornos, 0, 1, 1, 1 y 0: V(estudio) = 0.6. Discrepan sobre el pasillo:

Si el proceso es de Markov, la respuesta de TD debería predecir mejor los retornos futuros. El único mal resultado después del pasillo fue culpa del cargador, y cinco visitas al estudio dicen más sobre el cargador que una.

Esto ayuda a explicar por qué TD tiende a aprender más rápido. Calcular directamente la estimación de equivalencia de certeza rara vez es práctico: con n estados, el modelo solo puede necesitar memoria del orden de n², y resolverlo, unos n³ pasos. TD se acerca a la misma respuesta con memoria del orden de n, y TD en línea, que no repasa, igual avanza más o menos hacia ella.

El algoritmo

TD(0) por lotes, para un lote de episodios y un tamaño de paso α pequeño:

1. Parte con cualquier V(s), salvo V(terminal) = 0.
2. Con V fija, recorre cada paso de cada episodio del lote y calcula su TD error, δ_t = R_t+1 + γV(S_t+1) − V(S_t).
3. Cambia cada estimación una sola vez, α veces la suma de los TD errors de los pasos que parten en su estado: V(s) ← V(s) + α Σ δ_t, sobre los pasos con S_t = s.
4. Vuelve al paso 2 hasta que V deje de cambiar.

Monte Carlo por lotes es lo mismo con G_t − V(S_t) en lugar de δ_t, en cada paso, como en Monte Carlo con α constante.

La figura ejecuta ambos sobre los 702 movimientos de los 30 episodios de la primera figura, con todas las estimaciones en 0 y α = 0.005, pequeño porque cada estimación se mueve α veces una suma: 176 de los movimientos parten en A1.

• El agente no se mueve de A1, porque el lote solo se repasa.
• Cada vez que presionas Siguiente se ejecuta una línea de los pasos de arriba; las estimaciones que cambia una pasada tienen borde verde, y las que toman prestadas los objetivos, borde rojo, como en la primera figura.
• Los botones sobre la grilla cambian entre TD(0) por lotes y Monte Carlo por lotes.

5Sarsa: TD para control

Para aprender a actuar sin modelo, TD aprende valores de acción, y la política mejora en el camino: evaluar con TD, actuar de forma ε-greedy con respecto a las estimaciones actuales, y repetir, como en la iteración de políticas generalizada. La actualización es la misma de TD(0), de un par estado–acción al siguiente:

Se hace después de cada transición desde un estado no terminal, con Q(terminal, ·) = 0. Usa las cinco cantidades S_t, A_t, R_t+1, S_t+1 y A_t+1, que le dan su nombre al método. Sarsa es on-policy: A_t+1 es la acción que la política de verdad toma después, así que Sarsa aprende los valores de la política que sigue, exploración incluida.

Sarsa converge con probabilidad 1 a una política óptima y sus valores de acción si todos los pares se siguen visitando, los tamaños de paso se achican de la forma habitual y la política se vuelve greedy en el límite, por ejemplo ε-greedy con ε = 1/t.

El algoritmo

Para un tamaño de paso α en (0, 1] y un ε > 0 pequeño, con Q(s, a) arbitraria salvo Q(terminal, ·) = 0:

1. Al comienzo de cada episodio, observa S y elige A de forma ε-greedy con respecto a Q.
2. Toma A, y observa R y S′. Elige A′ en S′ de forma ε-greedy con respecto a Q.
3. Actualiza Q(S, A) ← Q(S, A) + α[R + γQ(S′, A′) − Q(S, A)].
4. Haz S ← S′ y A ← A′, y vuelve al paso 2 hasta que S sea terminal.

Aprender dentro del episodio es lo que le permite a Sarsa escapar de una política que nunca terminaría. Supón que todos los valores de acción del robot parten en 0 y que, al desempatar, su política lo manda del pasillo de vuelta a la cocina, desde donde el único movimiento es volver al pasillo. Seguida de forma greedy, esa política va y viene para siempre, y un método Monte Carlo esperaría para siempre un retorno. Con Sarsa, α = 0.5 y γ = 1:

1. La primera vez que el robot vuelve a la cocina, Q(pasillo, cocina) baja a 0.5(−1 + 0 − 0) = −0.5.
2. Eso queda por debajo del 0 del movimiento al estudio, que aún no ha probado.
3. Así que la próxima vez que está en el pasillo, se va al estudio.

Para ver aprender a Sarsa, toma una grilla más grande que la de la galleta:

• de 6 celdas de ancho y 4 de alto, desde A1 abajo a la izquierda hasta F4 arriba a la derecha;
• el agente parte en A1, y un episodio termina cuando llega a la meta, F1, abajo a la derecha;
• cada movimiento da −1, y entre el inicio y la meta, a lo largo del borde de abajo, hay un acantilado: un paso hacia él da −100 y devuelve al agente al inicio;
• la ruta más corta va justo por el borde, en 7 movimientos.

La figura ejecuta Sarsa ahí con α = 0.5, γ = 1 y ε = 0.1, así que en cada celda el movimiento greedy tiene probabilidad 0.925 y cada uno de los demás 0.025. Cada celda vuelve a guardar los valores de sus cuatro movimientos, como en la figura de control Monte Carlo. Aquí cada movimiento cuesta, así que los valores son negativos, y el mapa de calor los sombrea de un coral tenue, más intenso cuanto más negativos son. Antes de cada actualización, el agente elige su siguiente movimiento, en amarillo, y el objetivo usa el valor de ese movimiento, con borde rojo.

El objetivo de Sarsa usa el movimiento que el agente de verdad hace después, incluidos los de exploración, así que sus valores cuentan lo que cuesta explorar. Junto al borde, cada paso tiene una probabilidad de 0.025 de un movimiento al azar hacia abajo, al acantilado; una fila más arriba, un movimiento al azar hacia abajo solo cae en el borde. Eso hace que para Sarsa el borde valga menos.

En la figura, los valores todavía saltan con cada caída, porque α = 0.5 mueve una estimación la mitad del camino hacia cada objetivo. Con un tamaño de paso pequeño y muchos episodios, se asientan en los valores de la política ε-greedy que sigue el agente, que promedian cada caída:

La ruta una fila más arriba, de 9 movimientos, es lo mejor que puede hacer un agente que sigue explorando. No es la mejor ruta: cuando deja de explorar, el borde es dos movimientos más corto y nunca cae.

6Resumen

Las ideas clave junto a sus equivalentes en NumPy, con las tablas v y q indexadas por estado, y por estado y acción.