Predicción on-policy con aproximación

1Valores a partir de pesos

El apunte de eligibility traces escribió sus actualizaciones para cualquier estimación v(s, w), el valor del estado s dado un vector de pesos w, con una tabla como el caso más simple, un peso por estado. De aquí en adelante, los pesos son muchos menos que los estados. Cada estado se describe con un vector de features, d números calculados a partir del estado:

y la estimación más simple, la que usa este apunte, es lineal en los pesos: cada feature por su peso, sumadas.

Para el cart-pole, las features podrían ser los cuatro números del estado, o cualquier cosa calculada a partir de ellos. El agente de este apunte se queda con una sola: el ángulo del péndulo, cortado en seis rangos de 4° de −12° a 12°. Cada rango es una feature, 1 cuando el péndulo se inclina dentro de él y 0 si no, así que d = 6, y v(s, w) es simplemente el peso del rango en que está el péndulo.

Una tabla también es lineal, con una feature por estado, 1 en su propio estado y 0 en todos los demás. Elegir las features es elegir qué puede distinguir el agente. Este agente no puede distinguir un péndulo que vuelve hacia la vertical de uno que se cae, si se inclinan lo mismo. Cada estado igual recibe un valor, incluso uno nunca visto, siempre que se puedan calcular sus features. El precio es que una actualización ya no se queda donde se hace: cambiar un peso para corregir la estimación de un estado cambia la estimación de todos los estados con esa feature, aquí todos los estados de su rango.

Cada actualización de los apuntes anteriores movía la estimación de un estado S_t hacia un objetivo:

Cada par así, las features del estado y su objetivo, es ahora un ejemplo para aprendizaje supervisado, que ajusta una función a ejemplos de entradas y de las salidas deseadas para ellas. Cualquier método supervisado podría ajustar los pesos, siempre que:

• aprenda de ejemplos que llegan de a uno, a medida que el agente se mueve;
• tolere objetivos que cambian a medida que las estimaciones mejoran.

Este apunte usa el más simple, el descenso de gradiente.

2Qué errores importan

Con menos pesos que estados, las estimaciones no pueden estar todas bien, y mejorar una puede empeorar otras. Para elegir entre ellas, se pondera el error al cuadrado de cada estado según cuánto importa ese estado, con una distribución μ(s) ≥ 0, Σ_s μ(s) = 1. El resultado es el error cuadrático medio de valor (mean squared value error):

Su raíz cuadrada da una idea aproximada de cuán lejos están las estimaciones de los valores verdaderos.

En una tarea episódica se obtiene de dos cantidades: h(s), la probabilidad de que un episodio empiece en s, y η(s), el número de pasos que un episodio pasa en s en promedio. Se pasa tiempo en s cuando un episodio empieza ahí, o cuando un paso lleva ahí desde un estado donde se pasa tiempo:

Con descuento, un factor γ en el segundo término lo trata como una probabilidad de que el episodio termine. Empujado al azar, el péndulo pasa esta parte de su tiempo en cada rango:

Dentro de un rango los valores verdaderos difieren: un péndulo entre 4° y 8° que vuelve hacia la vertical puede seguir arriba 20 pasos más o más, y uno que se aleja, solo 2 o 3. Un peso no puede acertar en todos, y el VE pondera cada error según cuán seguido aparece su estado.

En la figura, cada punto es un estado que visitó la política, en su ángulo y su valor verdadero, los pasos que le quedaban en promedio; hay más puntos donde el péndulo pasa más tiempo. Arrastra las seis barras.

El VE es mínimo con cada barra en el promedio de los estados de su rango, ponderados por cuán seguido aparecen: unos 19 pasos en los rangos del centro, 12 de 4° a 8°, y 5 pasado 8°. Lo que queda, 22.8, un error típico de 4.8 pasos, es la dispersión dentro de los rangos, que solo mejores features podrían reducir. En la práctica nadie calcula μ: seguir π trae cada estado a estas tasas, así que aprender de los estados a medida que llegan pondera sus errores por μ.

El VE es la meta que usa este apunte, con dos advertencias:

• Una estimación lineal tiene un solo mínimo del VE; una estimación que no es lineal en sus pesos, como una red neuronal, puede tener muchos, y los métodos que siguen pueden entonces encontrar solo uno cercano a donde empiezan.
• No es seguro que el VE sea la meta correcta: los valores se quieren para elegir acciones, y los valores con el menor VE no son necesariamente los mejores para eso.

3Aprender de retornos

Supón por un momento que cada visita a un estado S_t viniera con su valor verdadero. Los pesos podrían entonces dar un paso pequeño en la dirección que más rápido reduce el error al cuadrado de ese estado, contra su gradiente:

El gradiente ∇v es el vector de las derivadas parciales de la estimación con respecto a los pesos. Dice qué pesos produjeron la estimación de S_t, y cuánto, y para una estimación lineal es el vector de features, ∇v(s, w) = x(s).

Los estados llegan a las tasas que fija μ, así que en muchos pasos pequeños los pesos bajan por el VE. Los pasos tienen que ser pequeños: pasos que eliminaran todo el error de cada estado solo perseguirían al último visitado. Con un tamaño de paso que se achica al ritmo adecuado, los pesos convergen a un mínimo del VE, o a uno de sus mínimos si tiene varios.

El valor verdadero es desconocido, así que la actualización usa un objetivo U_t en su lugar:

Si el objetivo acierta en promedio, E[U_t | S_t = s] = v_π(s), la garantía se mantiene. El retorno acierta en promedio por definición, ya que v_π(s) es el retorno que se espera desde s. Con U_t = G_t, la actualización es gradient Monte Carlo.

El algoritmo

Gradient Monte Carlo, para una política π, una estimación v diferenciable en sus pesos y un tamaño de paso α > 0:

1. Parte con cualquier vector de pesos w, por ejemplo con todos en 0.
2. Genera un episodio S₀, A₀, R₁, …, S_T−1, A_T−1, R_T siguiendo π.
3. Para cada paso, t = 0, 1, …, T − 1, actualiza w ← w + α[G_t − v(S_t, w)] ∇v(S_t, w).
4. Vuelve al paso 2 para el siguiente episodio.

Con agregación de estados, ∇v es 1 para el peso del rango de S_t y 0 para los demás, así que cada actualización mueve un peso, la estimación compartida de todo un rango, hacia el retorno de uno de sus estados.

La figura ejecuta gradient Monte Carlo en el cart-pole durante 2000 episodios:

• Arriba, el carro y el péndulo muestran el estado actual, y una flecha amarilla el empujón recién elegido.
• Abajo, el peso de cada rango es una barra, los pasos que se espera que el péndulo siga arriba, y un punto en el eje marca el ángulo actual del péndulo.
• α parte en 0.1 y se achica tras cada episodio, α = 0.1 · 20/(k + 19) en el episodio k, para que los pesos se asienten: estos métodos convergen cuando α se achica, y con α constante un solo episodio largo seguiría moviendo las barras varios pasos.

4Aprender de la estimación siguiente

TD(0) usa el objetivo U_t = R_t+1 + γv(S_t+1, w_t), construido con los mismos pesos, y eso tiene dos consecuencias:

1. El objetivo acierta en promedio solo si la estimación del estado siguiente acierta, así que es sesgado, y la garantía de la sección anterior ya no se aplica.
2. El paso de la sección anterior es el gradiente del error al cuadrado solo para un objetivo que no depende de los pesos. Este sí depende: cambiar los pesos cambia la estimación del estado siguiente, y con ella el objetivo.

La actualización toma en cuenta cómo los pesos mueven la estimación de S_t, e ignora cómo mueven el objetivo. Sigue solo una parte del gradiente, por eso se le llama un método semi-gradient:

En el cart-pole, el 85% de los pasos deja al péndulo en el rango en que estaba. El objetivo de un paso así es la recompensa, 1, más justo el peso que se actualiza, así que el TD error es 1 valga lo que valga ese peso, y la actualización sube juntos la estimación y el objetivo: persigue un objetivo que se mueve con ella.

¿Por qué usarlo, entonces? Por las razones del apunte de TD: aprende de cada paso sin esperar el final de un episodio, funciona en tareas que nunca terminan, y sus objetivos varían menos que los retornos, así que suele aprender más rápido. Y con una estimación lineal converge de forma confiable, a un punto que encuentra la próxima sección.

El algoritmo

Semi-gradient TD(0), para una política π, una estimación v diferenciable en sus pesos con v(terminal, ·) = 0, y un tamaño de paso α > 0:

1. Parte con cualquier vector de pesos w, por ejemplo con todos en 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 w ← w + α[R + γv(S′, w) − v(S, w)] ∇v(S, w).
5. Haz S ← S′, y vuelve al paso 3 hasta que S sea terminal.

La figura ejecuta semi-gradient TD(0) en los mismos episodios, con los mismos rangos y el mismo α. El objetivo de cada paso toma prestado el peso del rango del estado siguiente, con borde rojo, que suele ser el rango que se actualiza.

5Dónde termina cada método

Con una estimación lineal el gradiente es el vector de features, así que la actualización general queda

y cada peso se mueve en proporción a su propia feature. Un VE lineal tiene un solo mínimo, o, cuando algunas features solo repiten a otras, un conjunto de mínimos igual de buenos. Así, gradient Monte Carlo, con un tamaño de paso que se achica adecuadamente, converge a los pesos con el menor VE: en el cart-pole, el promedio de cada rango.

Semi-gradient TD(0) también converge, aunque no por el mismo argumento, ni a los mismos pesos. Escribiendo x_t por x(S_t), su actualización es

Promediando sobre los estados que visita la política y los pasos que da desde ellos, los pesos siguientes son

así que en promedio los pesos dejan de moverse donde b − Aw = 0:

Este es el fixed point de TD, y semi-gradient TD(0) lineal converge a él. Con agregación de estados tiene un sentido simple: el peso de cada rango es igual al promedio, sobre los pasos dados desde ese rango, de la recompensa más el peso del rango donde cae el paso (0 tras una caída). TD trata los rangos como si fueran los estados. No lo son: entre 4° y 8°, algunos péndulos vuelven hacia la vertical y otros se caen, y el rango del paso siguiente depende de cuál. TD toma prestado el mismo promedio para ambos, y termina 3.4 pasos sobre los promedios en los rangos del centro y cerca de 1 bajo ellos más afuera:

¿Qué tan lejos puede quedar el fixed point de TD? Para tareas continuas con γ < 1, se ha demostrado que

Con γ = 0.9, el error de TD es a lo más diez veces el mínimo, y la cota se afloja a medida que γ se acerca a 1; para tareas episódicas, como el cart-pole, vale una cota distinta pero relacionada. Lo que TD pierde en el límite, a menudo lo recupera en rapidez. Cuál método es mejor depende del problema, de las features y de cuánto dura el aprendizaje.

Entre los dos está n-step TD, cuya forma semi-gradient actualiza la estimación del estado n pasos atrás hacia el retorno de n pasos:

Mientras más recompensas reales tiene un objetivo, menos se apoya en las estimaciones, y más se acerca su fixed point a los promedios: en el cart-pole, 19.6 pasos en los rangos del centro con n = 8. Elige un método en la figura para ver dónde termina.

6Resumen

Las ideas clave junto a sus equivalentes en NumPy, para una estimación lineal. x y x_next son los vectores de features de S_t y S_t+1 (todos 0 para un estado terminal), xs tiene los vectores de features de todos los estados como filas, p_pi[s, s2] es la probabilidad de un paso de s a s2 bajo π, y v_pi, h y mu se indexan por estado. En n-step TD, rs tiene las n recompensas que siguen a S_t, y x_n el vector de features de S_t+n.