Model-based RL: R-Max y Dyna

1Modelos y planning

Los modelos son de dos tipos, y cualquiera de los dos puede tomar el lugar del ambiente y producir experiencia simulada. Las dinámicas p(s′, r | s, a) que supone la programación dinámica son un modelo de distribución:

Un modelo de distribución siempre puede producir muestras, así que es el más fuerte de los dos. Pero un modelo de muestra suele ser mucho más fácil de construir: una noche de diez viajes al cargador tiene 2¹⁰ = 1024 secuencias de libre y ocupado, y un modelo de distribución debe dar la probabilidad de cada una, mientras que un modelo de muestra simplemente juega los diez viajes.

El planning de estos apuntes pasa por valores, igual que el aprendizaje:

Ambos miran lo que sigue a un estado o a una acción, y llevan el resultado de vuelta a un valor. Por eso un método de aprendizaje normalmente también puede planear: solo necesita experiencia simulada en lugar de real.

Value iteration

Con un modelo de distribución, el agente puede resolver la ecuación de optimalidad de Bellman del apunte de Q-learning, algo que un agente sin modelo no puede hacer. Escrita para los valores de los estados, la ecuación se vuelve una actualización:

Value iteration la aplica a cada estado, barrido tras barrido, hasta que ningún valor cambie. Cada barrido le da a cada estado lo más que se puede esperar de su mejor acción, juzgado por los valores actuales de lo que sigue, así que la noticia de una recompensa viaja hacia atrás un paso por barrido. Los valores convergen a v_*(s) = max_a q_*(s, a), los valores óptimos del modelo, y actuar de forma greedy con respecto a ellos es la mejor conducta en el modelo. Value iteration es un método de programación dinámica.

En el modelo del robot, dejando de lado la puerta sin probar, cada pieza tiene un solo movimiento, así que cada máximo tiene un solo término. Así va value iteration sobre él, partiendo de 0, con cada barrido usando los valores del barrido anterior:

El estudio vale 0.6 · 1 + 0.4 · 0 = 0.6 desde el primer barrido, y la noticia llega al pasillo un barrido después, −1 + 0.6 = −0.4; el tercer barrido no cambia nada. Son los valores a los que convergió TD(0) por lotes en el apunte de TD, la estimación de equivalencia de certeza, calculados aquí directamente del modelo.

Q-planning

Con un modelo de muestra, el agente puede planear aprendiendo de pasos imaginados. El Q-planning tabular de un paso con muestras al azar repite tres pasos:

1. Elige al azar un estado S y una acción A.
2. Pídele al modelo de muestra una recompensa R y un siguiente estado S′.
3. Aplícales la actualización de Q-learning: Q(S, A) ← Q(S, A) + α[R + γ max_a Q(S′, a) − Q(S, A)].

Converge a la política óptima del modelo en las mismas condiciones en que Q-learning converge en el ambiente: cada par se sigue eligiendo, y el tamaño de paso se achica de forma adecuada. Si se le pregunta cinco veces por cargar en el estudio, el modelo de muestra podría responder +1, 0, +1, +1 y 0. Con α = 1/n en la n-ésima respuesta, la estimación del Q-planning es el promedio acumulado de las respuestas, y termina en 0.6, el valor que el modelo de distribución da de inmediato:

La figura ejecuta Q-planning en la grilla de la galleta del apunte de Monte Carlo, con un modelo que conoce todos los movimientos, como si al agente le hubieran dicho las reglas de la grilla. Ahí un movimiento siempre hace lo mismo, así que no hay nada que promediar: la figura usa α = 1, y cada paso fija el valor que actualiza en su objetivo.

• Los 32 valores parten en 0 y se ven todos, porque el modelo guarda todos los movimientos.
• El agente se queda en A1, y una copia tenue suya juega cada paso imaginado: aparece en el estado elegido, con el movimiento en amarillo, y va adonde el modelo dice que lleva el movimiento.
• La actualización tiene borde verde, hacia su objetivo en rojo, como en la figura de Q-learning.
• Después del primer paso, cada vez que presionas Siguiente se ejecuta un paso de planning completo.

Value iteration usa cada resultado que lista el modelo de distribución; el Q-planning, como Q-learning, usa un resultado a la vez y promedia mediante su tamaño de paso. Además, cada paso de Q-planning es pequeño, así que el planning puede interrumpirse o redirigirse en cualquier momento sin desperdiciar mucho cálculo. Eso importa cuando el planning se mezcla con la acción, como en Dyna, en la sección 3.

2R-Max: optimistas ante lo desconocido

R-Max aprende su modelo contando. Lleva N(s, a), el número de veces que ha tomado la acción a en el estado s, y N(s, a, s′, r), el número de esas veces que llevaron a s′ con recompensa r, y estima las dinámicas con la fracción de veces que ocurrió cada resultado:

El modelo del robot se hizo así: el cargador del estudio estaba libre en 3 de 5 visitas, así que P(fin, +1 | estudio, cargar) = 3/5. Es el modelo de máxima verosimilitud del apunte de TD. R-Max planea sobre él con value iteration, en cada paso, y actúa de forma greedy según los valores que obtiene. Usa su experiencia solo para mejorar el modelo; sus valores vienen del planning.

Contar deja una pregunta: ¿qué hacer con un par probado pocas veces, o nunca? El robot tiene N(pasillo, garaje) = 0, así que no existe ninguna fracción, y un planificador que dejara fuera la puerta nunca iría a mirar. R-Max responde con optimismo ante lo desconocido:

En la casa, R_max = 1, un cargador libre, así que value iteration valora la puerta del garaje en 1, contra −1 + 0.6 = −0.4 pasando por el estudio, y el robot va a mirar. En la figura, la puerta está al final de un corredor cuyos movimientos son known, cada uno con un costo de 1; arrástrala más lejos.

Los pares unknown demasiado lejos, o detrás de demasiados movimientos costosos, quedan sin explorar. El optimismo convierte la exploración en un asunto de planning: los valores envían al agente a lo desconocido por el camino más corto, y solo cuando podría valer la pena.

Supón que el robot, al mirar, encuentra en el garaje un segundo cargador, siempre libre. Una vez que la puerta y el cargador son known, el garaje vale −1 + 1 = 0 desde el pasillo, más que el estudio, y desde entonces carga ahí, mientras que un planificador que dejara fuera la puerta seguiría yendo al estudio.

El número k fija en cuánto se apoya cada estimación. Donde una acción siempre tiene el mismo resultado, como en la grilla de abajo, una visita lo dice todo, y k = 1 basta. Donde los resultados varían, pocas visitas pueden engañar:

1. Un cargador libre 3 de cada 5 veces está ocupado en una sola visita 2 de cada 5 veces.
2. Con k = 1, el modelo dice entonces que nunca está libre.
3. El par es known, así que nada manda al robot de vuelta a comprobarlo, y podría conformarse con un cargador peor.

Mientras más visitas pide k, menos probable es que todas lo encuentren ocupado:

Con el tiempo, todo par que valga la pena conocer se vuelve known, y R-Max sigue la mejor política de su modelo. R-Max, propuesto por Brafman y Tennenholtz en 2002, converge a una política near-optimal, con una brecha que depende de k, en un número de pasos que crece solo de forma polinomial con el tamaño del problema.

El algoritmo

Para un número de visitas k y una recompensa R_max al menos tan grande como cualquier recompensa que pueda dar el mundo:

1. Pon cada conteo en 0: N(s, a) ← 0 y N(s, a, s′, r) ← 0.
2. Al comienzo de cada episodio, observa el primer estado S.
3. Corre value iteration sobre el modelo, en el que un par known, con N(s, a) ≥ k, lleva a s′ con recompensa r con probabilidad N(s, a, s′, r)/N(s, a), y un par unknown da R_max y termina el episodio.
4. Elige A de forma greedy según V: la acción con el mayor Q(S, a) = Σ_{s′, r} P(s′, r | S, a)[r + γV(s′)], que es R_max para una acción unknown.
5. Toma A, y observa R y S′.
6. Cuéntalo: N(S, A) ← N(S, A) + 1 y N(S, A, S′, R) ← N(S, A, S′, R) + 1.
7. Haz S ← S′, y vuelve al paso 3 hasta que S sea terminal.

La figura ejecuta R-Max en la grilla de la galleta, con k = 1, R_max = 1, la recompensa de la galleta, y γ = 0.9. Cada triángulo tiene el valor de un movimiento, Q(s, a) como lo calcula el paso 4:

• un movimiento sin probar está sombreado de gris y tiene el 1 que R-Max supone para él;
• un movimiento known tiene su recompensa más 0.9 veces el valor de la celda adonde lleva.

Cada vez que presionas Siguiente se ejecuta una línea del algoritmo: el agente elige un movimiento, en amarillo, lo toma, lo cuenta, en verde, y value iteration corre sobre el nuevo modelo, lo que quita la sombra.

En la figura, el modelo cambia solo cuando un movimiento se vuelve known, así que en todos los demás pasos value iteration devuelve los valores que ya tenía. Correrlo en cada paso es la forma más simple de escribir R-Max, no la más barata: una versión eficiente vuelve a planear solo cuando el modelo cambia.

3Dyna: aprender, planear y actuar a la vez

Un agente que planea mientras actúa puede usar cada paso real de dos maneras: para mejorar su modelo, de modo que se parezca más al mundo, y para mejorar sus valores y su política directamente, con los métodos de aprendizaje de los apuntes anteriores. La primera se llama aprendizaje del modelo (model learning), y la segunda, aprendizaje reforzado directo, o RL directo (direct RL). A través del modelo, la experiencia también mejora los valores de forma indirecta, mediante el planning.

R-Max usa su experiencia solo para el modelo, y Q-learning solo para los valores. Cada forma tiene sus ventajas:

• el planning saca más provecho de una cantidad limitada de experiencia, así que llega a una buena política con menos pasos reales;
• el aprendizaje directo es más simple, y un modelo equivocado no puede engañarlo.

Dyna hace todo a la vez: actuar, aprender el modelo, RL directo y planning. Su planning aplica el mismo método de aprendizaje a los pasos simulados que a los reales, así que el aprendizaje y el planning comparten casi todo, salvo de dónde viene su experiencia. El agente es siempre reactivo y siempre deliberativo: actúa de inmediato según sus valores más recientes, mientras el planning sigue de fondo. Cuando el modelo aprende algo nuevo, el planning que sigue lo incorpora a los valores.

Dyna-Q, el Dyna más simple, es Q-learning tabular de un paso, su RL directo, con dos partes agregadas:

• un modelo, una tabla que guarda, para cada par que el agente ha probado, la recompensa y el estado siguiente que vio después la última vez, que es todo lo que hay que saber en un mundo donde una acción siempre tiene el mismo resultado;
• planning, Q-planning de un paso con muestras al azar, n pasos después de cada paso real. Su control de búsqueda (search control), la regla que decide qué pasos simulados dar, elige estados en los que el agente ha estado y acciones que ha tomado ahí, así que nunca se le pregunta al modelo por un par del que no sabe nada.

El algoritmo

Dyna-Q tabular, para un tamaño de paso α en (0, 1], un ε > 0 pequeño y un número de pasos de planning n, con todo Q(s, a) en 0 y el modelo vacío:

1. Observa el estado actual S, y elige A de forma ε-greedy según Q.
2. Toma A, y observa la recompensa R y el siguiente estado S′.
3. Actualiza Q(S, A) ← Q(S, A) + α[R + γ max_a Q(S′, a) − Q(S, A)].
4. Recuerda lo que pasó: Model(S, A) ← R, S′.
5. Planea, n veces: elige al azar un estado visto antes y una acción tomada ahí antes, obtén R y S′ de Model, y aplícales la actualización del paso 3.
6. Si S′ es terminal, un nuevo episodio parte en su primer estado. Vuelve al paso 1.

La figura ejecuta Dyna-Q en la grilla de la galleta con α = 0.5, ε = 0.1, γ = 0.9 y n = 10. Sus marcas son las de la figura de Q-learning, y sus pasos de planning se ven como en la figura de la sección 1. Como ahí, los triángulos con un número son los movimientos que guarda el modelo, 0 incluido, pero este modelo parte vacío: un movimiento muestra su valor una vez que el agente lo probó. El movimiento recién recordado tiene borde azul.

Después del primer episodio de la figura, los métodos difieren en cuántos movimientos del episodio reciben crédito:

El planning lleva el valor de la galleta hacia atrás por cada movimiento recordado, y pedazos de recorridos distintos se juntan en rutas que nunca se recorrieron de una vez. Con más pasos de planning por movimiento, los valores se asientan en menos episodios, al precio de más cálculo por movimiento.

R-Max y Dyna

Las dos figuras muestran la diferencia en la exploración. R-Max probó los 32 movimientos de la grilla en sus primeros tres episodios, y después nunca volvió a explorar. Dyna-Q probó 15 de ellos en 30 episodios, y sigue haciendo un movimiento al azar una vez de cada diez.

4Cuando el modelo está equivocado

Hasta ahora los modelos han sido correctos: en la grilla, un movimiento known hace lo que dice el modelo. Un modelo puede estar equivocado por tres razones:

• el mundo es aleatorio y se ha visto pocas veces, como un cargador visitado una vez;
• el modelo generaliza de unos estados a otros, de forma imperfecta;
• o el mundo cambió desde que el modelo lo aprendió.

Planear con un modelo equivocado da una política buena para el modelo, y posiblemente mala para el mundo. Algunos errores se corrigen solos; otros son más difíciles:

• Cuando un modelo es optimista, y predice más recompensa o mejores movimientos de los que permite el mundo, la política planeada va a buscarlos, descubre que no están, y la experiencia que obtiene corrige el modelo. El optimismo de R-Max, en la sección 2, es un error así, cometido a propósito: su modelo promete R_max por cada movimiento que no ha probado, y probarlo lo corrige.
• Cuando el mundo se vuelve mejor de lo que cree el modelo, la política que recomienda el modelo puede no ir nunca adonde está la mejora, y el error puede durar mucho tiempo, o para siempre.

De vuelta en la casa del robot, el mundo cambia en ambas direcciones. Una noche cierran con llave la puerta del garaje, así que el movimiento que siempre llevaba al garaje ahora deja al robot en el pasillo, con un costo de 1. Y un día abren una puerta trasera del pasillo, que el robot probó una vez y encontró cerrada, con un cargador justo detrás; nada en ninguno de los dos modelos apunta ahí.

El modelo de Dyna-Q guarda el último resultado visto, y el de R-Max cuenta cada resultado desde el comienzo, viejo y nuevo:

La figura pone a ambos métodos en el acantilado del apunte de TD, γ = 1: R-Max con k = 1 y R_max = −1, la mayor recompensa ahí, y Dyna-Q con los parámetros de la figura de la sección 3. Su primer paso juega rápido sus primeros 10 episodios, después de los cuales ambos siguen el borde. Luego se levanta una pared entre A2 y B2, cruzando el borde, antes del episodio 11, y cae antes del episodio 21. Los botones sobre la grilla cambian de método; sus marcas son las de las secciones 2 y 3, y la pared se dibuja en tinta.

5Resumen

Las ideas clave junto a sus equivalentes en NumPy. En R-Max, n_sa[s, a] guarda N(s, a), y n_sasr[s, a, s2, i] guarda N(s, a, s′, r) para la i-ésima recompensa posible, rewards[i]; en Dyna-Q, model asocia cada par con lo que lo siguió, seen lista los estados visitados, y taken[s] las acciones tomadas en s.