Predicción y control con Monte Carlo

1Promediar retornos

Una política π dice cómo elige el agente sus acciones; aquí, los movimientos al azar del robot. El valor de un estado bajo π es el retorno que cabe esperar desde él, la suma de las recompensas hasta que el episodio termina en el tiempo T, descontadas por γ:

Un valor esperado se puede estimar con un promedio de muestras, y cada visita a s en un episodio da una muestra: el retorno que vino después. Un estado se puede visitar más de una vez en el mismo episodio, así que hay dos formas de promediar:

En la casa γ = 1 y cada movimiento da −1, así que un retorno es menos el número de movimientos que quedan. Estos son dos viajes:

Monte Carlo first-visit toma, de cada viaje, el retorno después de la primera visita a una pieza: −3 y −7 para la cocina, que promedian −5. En el segundo viaje el robot vuelve a la cocina con 5 movimientos por delante, y Monte Carlo every-visit toma además ese −5: (−3 − 7 − 5)/3 también es −5. Difieren en el pasillo: every-visit promedia cuatro retornos, (−2 − 6 − 4 − 2)/4 = −3.5, y first-visit dos, (−2 − 6)/2 = −4.

Dos viajes cortos son una mala muestra: los valores reales son mucho más bajos, porque muchos viajes van y vuelven un buen rato. Salen de las relaciones entre piezas vecinas: cada pieza vale el promedio, sobre sus movimientos, de −1 más el valor de la pieza a la que lleva el movimiento, 0 en el cargador:

que juntas dan −9, −8 y −5. Promediar más viajes llega ahí: después de 10 000 viajes, ambos métodos están a menos de 0.1 de estos valores.

Ambos métodos convergen a v_π(s) a medida que crece el número de visitas, cada uno por su propia razón:

• Para Monte Carlo first-visit es la ley de los grandes números: cada retorno es una muestra independiente cuya esperanza es v_π(s), así que el promedio es insesgado, y su error se achica como 1/√n después de n retornos.
• Monte Carlo every-visit también converge, aunque sus muestras de un mismo episodio no son independientes.

El algoritmo

Los retornos son más fáciles de calcular hacia atrás desde el final del episodio, porque G_t = R_t+1 + γG_t+1. Predicción Monte Carlo first-visit, para una política π:

1. Parte con cualquier estimación V(s) y una lista vacía de retornos para cada estado.
2. Genera un episodio siguiendo π: S₀, A₀, R₁, …, S_T−1, A_T−1, R_T. Haz G ← 0.
3. Para t = T − 1, T − 2, …, 0: haz G ← γG + R_t+1. Si S_t no aparece antes en el episodio, agrega G a los retornos de S_t y deja V(S_t) en su promedio.
4. Repite desde el paso 2 con cada nuevo episodio. Monte Carlo every-visit es igual, sin la revisión del paso 3.

La figura lo ejecuta en una grilla de 3 celdas de ancho y 3 de alto, con las celdas nombradas por columna y fila, desde A1 abajo a la izquierda hasta C3 arriba a la derecha, con todas las estimaciones en 0:

• un agente parte en A1 y se mueve arriba, a la derecha, abajo o a la izquierda, cada movimiento elegido al azar por la política; un movimiento contra una pared deja al agente donde está;
• llegar a la galleta en C3 da +1 y termina el episodio, y cualquier otro movimiento da 0, así que con γ = 0.9 el retorno desde una celda es 1 si el siguiente movimiento llega a la galleta, 0.9 si llega un movimiento después, 0.81 si dos, y así.

Cada celda muestra su estimación, sombreada de verde cuanto más cerca de 1 está, y nada en 0. El pseudocódigo junto a la grilla ilumina la línea que ejecuta cada paso. Al principio, cada vez que presionas Siguiente se ejecuta una línea del algoritmo:

• durante el episodio, el movimiento elegido se pone amarillo y el agente lo toma, las celdas que va dejando tienen un borde azul punteado, y ninguna estimación cambia;
• cuando el agente llega a la galleta, cada vez se da un paso del recorrido hacia atrás, y cada estimación que actualiza tiene un borde verde.

Más adelante, Siguiente salta a los momentos en que se aprende algo nuevo, y el botón del engranaje, después de Siguiente, abre los ajustes de la figura: el mapa de calor y el sonido.

Promediar sobre la marcha

No hace falta guardar todos los retornos. Después de un nuevo retorno G_t, el promedio de los N(S_t) retornos vistos hasta ahora se mueve hacia él:

Para el pasillo, el primer retorno, −2, da V = −2, y el segundo, −6, da −2 + ½(−6 + 2) = −4, el mismo promedio de antes. Un paso constante α en lugar de 1/N da Monte Carlo con α constante, V(S_t) ← V(S_t) + α[G_t − V(S_t)], que, como el α constante del apunte de bandits, sirve en problemas que cambian con el tiempo, por ejemplo aprender sobre una política que sigue cambiando.

Sin bootstrapping

Una consecuencia es que estimar un estado cuesta lo mismo sin importar cuántos estados haya, así que un método Monte Carlo puede estudiar unos pocos estados de interés partiendo muchos episodios desde ellos e ignorando el resto. El precio es esperar: una estimación cambia solo cuando termina su episodio.

2Valores de acciones

Los valores de estado bastan para elegir acciones solo con un modelo del mundo: sabiendo que un movimiento desde el pasillo lleva al estudio, el robot podría comparar las piezas a las que lleva cada movimiento. Sin modelo necesita directamente el valor de cada acción:

el retorno que cabe esperar después de tomar la acción a en el estado s y seguir π desde ahí. Monte Carlo lo estima igual que antes, promediando los retornos después de las visitas al par (s, a), first-visit o every-visit. Para el robot que anda al azar, cada movimiento vale su −1 más el valor de la pieza a la que lleva:

La complicación es que puede haber muchos pares que nunca se visiten. Un robot que siempre fuera del estudio directo al cargador nunca vería un retorno por volver al pasillo, y nunca podría saber si ese movimiento es mejor o peor. Para comparar acciones, hay que seguir probando todos los pares.

Una forma de garantizarlo son los exploring starts (inicios exploratorios): cada episodio parte en un par estado–acción elegido al azar, con alguna probabilidad para cada par. Eso es fácil en una simulación y casi siempre imposible en el mundo real, donde los episodios parten donde parten.

3Mejorar la política

Con valores de acción, una política mejor es fácil de encontrar: en cada estado, toma la acción de mayor valor. Una política que hace eso con respecto a q es greedy:

La política greedy es al menos tan buena como π en todas partes. El argumento tiene dos partes:

1. Seguirla un paso y luego seguir π vale max_a q_π(s, a), que es al menos v_π(s), el valor de seguir π todo el tiempo.
2. Por el teorema de mejora de políticas, seguirla en todos los pasos también es al menos igual de bueno.

En la casa, la política greedy toma en cada pieza el mejor movimiento del diagrama de arriba, al estudio desde el pasillo (−6 le gana a −10) y al cargador desde el estudio (−1 le gana a −9), y esa es la mejor política:

Aquí bastó un paso de mejora para llegar a la mejor política; en general, evaluación y mejora tienen que alternarse.

La evaluación no tiene que ser completa: los métodos Monte Carlo alternan después de cada episodio, actualizando los valores de los pares visitados y luego la política en esos estados.

El algoritmo

Monte Carlo con Exploring Starts, Monte Carlo ES:

1. Parte con cualquier Q(s, a), una lista vacía de retornos para cada par y cualquier política π.
2. Elige S₀ y A₀ al azar, con alguna probabilidad para cada par, y genera un episodio desde ellos siguiendo π: S₀, A₀, R₁, …, S_T−1, A_T−1, R_T. Haz G ← 0.
3. Para t = T − 1, T − 2, …, 0: haz G ← γG + R_t+1. Si el par S_t, A_t no aparece antes en el episodio, agrega G a sus retornos, deja Q(S_t, A_t) en su promedio y vuelve π greedy en S_t: π(S_t) ← argmax_a Q(S_t, a).
4. Repite desde el paso 2 con cada nuevo episodio.

No puede quedarse en una política que no sea óptima: los valores convergerían a los de esa política, y el paso greedy la cambiaría. Que siempre converja al óptimo es algo que se cree ampliamente, pero no se ha demostrado formalmente.

4Control sin exploring starts

Sin exploring starts, la única forma de seguir probando todas las acciones es que la propia política las siga eligiendo. Hay dos maneras de hacerlo, y esta sección trata de un método on-policy:

La política se mantiene blanda (soft), con π(a|s) > 0 para toda acción. Una política ε-soft le da a cada acción al menos ε/|𝒜(s)|, donde |𝒜(s)| es el número de acciones en s.

La más cercana a greedy entre ellas es ε-greedy:

El control Monte Carlo first-visit on-policy es Monte Carlo ES con un cambio: los episodios parten donde parten, y el paso de mejora vuelve la política ε-greedy con respecto a Q en vez de greedy.

El algoritmo

Control Monte Carlo first-visit on-policy, para un ε > 0 pequeño:

1. Parte con cualquier Q(s, a), una lista vacía de retornos para cada par y π ε-greedy con respecto a Q.
2. Genera un episodio siguiendo π: S₀, A₀, R₁, …, S_T−1, A_T−1, R_T. Haz G ← 0.
3. Para t = T − 1, T − 2, …, 0: haz G ← γG + R_t+1. Si el par S_t, A_t no aparece antes en el episodio, agrega G a sus retornos, deja Q(S_t, A_t) en su promedio y vuelve π ε-greedy en S_t con respecto a Q.
4. Repite desde el paso 2 con cada nuevo episodio.

La figura lo ejecuta en la grilla de la galleta de la sección 1, con ε = 0.1 y todos los valores partiendo en 0, y sus pasos funcionan como ahí, con movimientos en lugar de celdas:

• cada celda se divide en cuatro triángulos, uno por movimiento, cada uno con el valor de ese movimiento, en blanco mientras no se ha probado;
• cuando un movimiento vale más que los demás, su valor va en negrita, y de los cuatro pequeños triángulos del centro de la celda, en azul tenue, el que apunta hacia él se vuelve azul intenso;
• los movimientos de un episodio tienen un borde azul punteado, y los valores que actualiza su recorrido, uno verde;
• y el mapa de calor sombrea el triángulo de cada movimiento o, si se elige en los ajustes, cada celda según su mejor valor.

El paso ε-greedy igual mejora la política. Para cualquier π ε-soft, la política ε-greedy π′ con respecto a q_π cumple, en todo estado,

porque π′ pone su peso extra en el mayor q_π(s, a), y un promedio ponderado nunca supera a su mayor término. Por el teorema de mejora de políticas, π′ es al menos tan buena como π. En el estudio, con ε = 0.2 y dos acciones, π′ va al cargador con probabilidad 0.9: 0.9(−1) + 0.1(−9) = −1.8, muy por encima del −5 del robot que anda al azar.

¿Dónde termina? El proceso deja de mejorar solo en la mejor política ε-soft, que no es la mejor política: sigue explorando para siempre, y explorar cuesta. En la casa, en torno a los mejores movimientos:

Dejar que ε se achique con el tiempo cierra esa brecha.

5Resumen

Las ideas clave junto a sus equivalentes en NumPy. r[t+1] guarda R_t+1, s los estados de un episodio, y v, q y n las estimaciones y los conteos de visitas.