Bandits de múltiples brazos

1Valores de las acciones

Sea A_t el lugar donde se pesca la mañana t y R_t su pesca. Cada lugar a tiene un valor, la pesca que cabe esperar al pescar en él:

En el lago, q_*(muelle) = 1, q_*(juncos) = 3, q_*(rocas) = 4 y q_*(puente) = 2 peces por mañana. Su estimación en la mañana t, Q_t(a), es el promedio de las pescas que el lugar ha dado hasta entonces:

Aquí 𝟙_Ai=a vale 1 si se pescó en el lugar a la mañana i y 0 si no, así que ambas sumas conservan solo las mañanas pasadas en a. Un lugar donde nunca se ha pescado recibe una estimación por defecto, como 0. Mientras más se pesca en un lugar, más se acerca su promedio a q_*(a), por la ley de los grandes números: el promedio de más y más muestras se asienta en su media. Este es el método del promedio muestral.

La forma más simple de elegir es greedy: pescar en el lugar con la mayor estimación, la acción greedy, desempatando al azar.

Una pescadora ε-greedy es greedy la mayoría de las mañanas, pero con una probabilidad pequeña ε elige un lugar al azar entre los k, incluido el greedy. El lugar greedy se pesca entonces con probabilidad 1 − ε + ε/k, y cada uno de los otros con ε/k. Con k = 4 y ε = 0.2:

• el lugar greedy recibe 0.85 y cada uno de los otros 0.05;
• cuando dos lugares empatan en la mayor estimación, se reparten el 0.8 de las mañanas greedy, así que cada uno recibe 0.4 + 0.05 = 0.45, y los otros dos conservan 0.05.

Una pescadora greedy que parte con todas las estimaciones en 0 puede dejar de explorar tras una sola mañana:

1. La primera mañana las cuatro estimaciones valen 0, y el empate se rompe al azar.
2. Una pesca nunca es negativa, así que si la primera es mayor que cero, la estimación de ese lugar sube sobre 0 mientras las otras tres siguen en 0.
3. Su promedio sigue sobre 0 pesque lo que pesque después, así que los otros lugares nunca se vuelven a probar.

La figura sigue una de esas temporadas. Cada fila es una mañana, con las cuatro estimaciones antes de ella; el lugar donde se pesca está sombreado en amarillo, y su pesca, en rojo.

En 1000 temporadas de 300 mañanas, 9 de cada 10 temporadas greedy nunca dejan su primer lugar (en las demás no se pescó nada la primera mañana, así que el empate siguió abierto), y greedy pesca en las rocas cerca del 29% de las mañanas durante toda la temporada. Explorar lo arregla:

La última columna es lo que pescaría cada una con estimaciones exactas: 4 con greedy, lo mejor posible, pescando en las rocas cada mañana, y menos con ε, ya que explorar todavía la manda a lugares peores algunas mañanas. Con ε = 0.2 encuentra antes las rocas, y pesca en ellas el 76% de las mañanas 91–100, contra el 62% con ε = 0.05, pero más avanzada la temporada sus muchas mañanas al azar le cuestan más. Explorar cuesta peces hoy y rinde después.

2Promediar sobre la marcha

Promediar todas las pescas significa guardar todas las pescas. El promedio puede, en cambio, actualizarse tras cada una, guardando un número y un conteo por lugar. Toma un solo lugar y cuenta sus propias mañanas: R_i es ahora la pesca de su i-ésima mañana, y Q_n su estimación después de haber pescado en él n − 1 veces:

Las primeras n − 1 pescas suman (n − 1)Q_n, así que tras la n-ésima pesca el promedio es Q_n+1 = [R_n + (n − 1)Q_n]/n, que se reordena como

Vale también para n = 1, y da Q₂ = R₁ sea cual sea la conjetura inicial Q₁. Ahora hay dos contadores en juego: t cuenta las mañanas de la temporada, y n las mañanas en un lugar. En seis mañanas, para las rocas:

Las rocas terminan en 4, el promedio simple de 5, 3, 6 y 2. Cada fila de la tabla tiene la misma forma:

El corchete es un error, cuán lejos está la estimación del objetivo, aquí la última pesca. Una sola pesca es un objetivo ruidoso, pero en promedio apunta en la dirección correcta, y el tamaño de paso, aquí 1/n, fija cuánto moverse. Cada método de estos apuntes mueve una estimación un paso hacia un objetivo; los apuntes de Monte Carlo y de TD lo hacen con otros objetivos. Un tamaño de paso se escribe α, o α_n(a) cuando cambia de una pesca a la siguiente.

El algoritmo

Un algoritmo de bandit simple, ε-greedy con promedios muestrales:

1. Para cada lugar a, haz Q(a) ← 0 y N(a) ← 0.
2. Elige A: con probabilidad 1 − ε, el lugar con la mayor Q, desempatando al azar; con probabilidad ε, un lugar al azar.
3. Pesca en A y observa la pesca R.
4. Haz N(A) ← N(A) + 1 y Q(A) ← Q(A) + [R − Q(A)]/N(A).
5. Repite desde el paso 2 cada mañana.

3Cuando los peces se mueven

Un promedio muestral pesa la primera pesca tanto como la última. Eso es correcto mientras los lugares no cambien, pero un lago cambia, en contra del «no cambia con el tiempo» del problema de bandit definido arriba. En un problema no estacionario los valores reales cambian mientras el agente juega, y las recompensas recientes merecen más peso. La forma usual de dárselo es un tamaño de paso constante α, con 0 < α ≤ 1:

Reescrita como αR_n + (1 − α)Q_n, puede desenrollarse sustituyendo Q_n por su propia actualización, luego Q_n−1, y así hasta Q₁:

Es un promedio ponderado del inicio y de cada pesca. Cada actualización multiplica la estimación anterior por 1 − α, así que el peso de una pesca se achica en ese factor con cada pesca posterior. Los pesos de las pescas forman una suma geométrica, α[1 + (1 − α) + ⋯ + (1 − α)ⁿ⁻¹] = 1 − (1 − α)ⁿ, así que junto con el (1 − α)ⁿ de Q₁ suman 1.

Con α = 0.25 y Q₁ = 0, las cuatro pescas de las rocas de la sección 2 (5, 3, 6 y 2) dan estimaciones de 1.25, 1.69, 2.77 y 2.57. La figura muestra los pesos en la última.

Ahora el agua se entibia en la mañana 151: los peces dejan las rocas por los juncos, la media de las rocas cae de 4 a 1 y la de los juncos sube de 3 a 5. Para comparar el promedio muestral con α = 0.25 sin nada más en juego, supón que la pescadora sigue pescando en las rocas y que cada pesca es exactamente la media.

Con pescas aleatorias y ε = 0.2, en 1000 temporadas, la fracción de mañanas en el mejor lugar (las rocas hasta que el agua se entibia, los juncos después) es:

Antes de que el agua se entibie, al promedio muestral le va un poco mejor, ya que sus estimaciones son menos ruidosas. Después, el promedio muestral sigue volviendo a las rocas, y de la mañana 151 a la 300 pesca 3.46 peces por mañana, contra 4.34 con α = 0.25.

Las dos actualizaciones son una sola, con un tamaño de paso α_n(a) que puede cambiar de una pesca a otra:

Con α_n(a) = 1/n es el promedio muestral, y con un α constante, el que privilegia lo reciente. Las estimaciones convergen a los valores reales, con probabilidad 1 (en todas las temporadas salvo las de una mala suerte imposible), cuando

La primera suma debe crecer sin límite, para que los pasos siempre puedan superar el inicio y las pescas desafortunadas; la segunda debe quedar finita, para que los pasos terminen siendo lo bastante pequeños como para asentarse. Los promedios muestrales cumplen ambas: la suma de 1/n llega a 7.49 en n = 1000 y sigue creciendo, mientras que la suma de 1/n² se queda bajo 1.645. Un α constante no cumple la segunda, así que sus estimaciones nunca se asientan y siguen las últimas pescas, que es lo que necesita un lago que cambia. Las secuencias de pasos que cumplen ambas suelen aprender lento o requerir ajuste, y como la mayoría de los problemas cambian con el tiempo, un α constante es la elección usual en la práctica.

4Inicios optimistas

Todos los métodos vistos hasta aquí dependen de las estimaciones iniciales Q₁(a): están sesgados por ellas, con sus estimaciones arrastradas hacia el inicio y, por lo tanto, en promedio, desviadas de q_*(a). Cuánto dura el sesgo depende del tamaño de paso:

• con promedios muestrales desaparece tras la primera pesca de un lugar, ya que Q₂ = R₁;
• con un α constante solo se achica, como (1 − α)ⁿ: desde Q₁ = 8, las pescas 5, 3, 6 y 2 con α = 0.25 aún dan 5.11, y 2.53 de eso es el inicio.

Así que el inicio es una elección, una forma de introducir conocimiento previo o de impulsar la exploración. La pescadora greedy de la sección 1 partió en 0, bajo el valor de cada lugar, y se quedó en su primer lugar. Un α constante no la habría liberado: una pesca de 0 solo multiplica su estimación por 1 − α, así que nunca vuelve a 0. Si, en cambio, parte en 8, sobre la media de cada lugar, casi toda pesca decepciona, y la elección greedy se va a los lugares que siguen en 8, hasta que todos se han probado. La figura se dibuja como la de la sección 1.

En 1000 temporadas, la fracción de las mañanas 291–300 pasadas en las rocas:

Con promedios muestrales, el optimismo consigue cerca de un intento en cada lugar (una primera pesca de 8 o más, que es rara, mantiene a un lugar en carrera), y una primera pesca desafortunada aún puede enterrar a las rocas para siempre. Con α = 0.25, el optimismo se desvanece en varias pescas y mantiene a la pescadora probando por más tiempo. Las dos últimas filas comparten tamaño de paso, así que son la comparación justa, y gana el inicio optimista.

Solo ayuda una vez, al principio. Si el agua se entibia en la mañana 151, el inicio ya se olvidó, y nada en él manda a la pescadora a buscar lo que cambió. Una tercera forma de dirigir la exploración, la selección por cota superior de confianza (UCB), prefiere los lugares cuyas estimaciones aún son inciertas porque se ha pescado poco en ellos; este apunte no entra en ella.

5Preferencias en vez de valores

En vez de estimar valores, la pescadora puede aprender una preferencia H_t(a) por cada lugar y elegir los lugares con probabilidades que crecen con ella, mediante un softmax, cuya exponencial hace positiva cada probabilidad y cuya división por la suma hace que sumen 1:

Solo importan las diferencias entre preferencias: el softmax de 0.3, −0.1, 0.5 y 0 es 0.275, 0.185, 0.336 y 0.204, y sumar 5 a cada preferencia no lo cambia. Las preferencias parten iguales, aquí en 0, así que cada lugar parte con 0.25. Tras cada mañana se actualizan:

Aquí R_t, el baseline, es el promedio de las pescas antes de la mañana t, con R₁ ≐ R₁. Una pesca sobre el baseline sube la preferencia del lugar donde se pescó y baja las de los otros; una pesca bajo él hace lo contrario. Los otros se mueven según sus probabilidades, que suman 1 − π_t(A_t), exactamente lo que se mueve el lugar donde se pescó, así que la suma de las preferencias nunca cambia: si parte en 0, sigue en 0. Al repetir las seis mañanas de la sección 2, con los mismos lugares y pescas, y α = 0.1:

• La mañana 1 no cambia nada, ya que R₁ = R₁.
• La mañana 5 es una pesca de 6 en las rocas contra un baseline de 2.75, el promedio de 2, 5, 3 y 1, y π(rocas) sube de 0.319 a 0.387.
• La mañana 6 es una pesca de 2 contra un baseline de 3.4, y π(rocas) baja a 0.360. Si solo la mañana 6 no hubiera usado baseline, la misma pesca de 2 la habría subido a 0.426.

El baseline hace que una pesca cuente como buena o mala en comparación con la pesca habitual. Sin él, toda pesca de un pez o más sube al lugar donde se pescó, incluidos los lugares malos, y la pescadora distingue los lugares más lentamente. En 1000 temporadas:

Por qué funciona la actualización

La actualización es ascenso de gradiente estocástico sobre la pesca esperada. El ascenso de gradiente exacto movería cada preferencia según la pendiente de la recompensa esperada:

Los valores q_*(x) son desconocidos, así que esta pendiente no se puede calcular. Cuatro pasos muestran que la actualización de arriba la sigue en promedio:

1. Un baseline no agrega nada. Los valores q_*(x) no dependen de las preferencias, así que la pendiente solo alcanza a las probabilidades: ∂E[R_t]/∂H_t(a) = Σ_x q_*(x) ∂π_t(x)/∂H_t(a). Las probabilidades siempre suman 1, así que sus cambios suman 0: Σ_x ∂π_t(x)/∂H_t(a) = 0. Por eso se puede restar cualquier número B_t que no dependa de x:
   ∂E[R_t]∂H_t(a) = Σ_x (q_*(x) − B_t) ∂π_t(x)∂H_t(a)
2. La suma se vuelve una esperanza. Multiplicar cada término por π_t(x)/π_t(x) lo pondera por la probabilidad de pescar en x, lo que convierte la suma en un valor esperado sobre el lugar elegido, A_t:
   = E[(q_*(A_t) − B_t) ∂π_t(A_t)∂H_t(a) / π_t(A_t)]
3. Lo observado reemplaza a lo desconocido. Elige B_t = R_t, que se construye con las pescas anteriores a t y por eso no depende del lugar elegido en t. Luego pon la pesca R_t en lugar de q_*(A_t). Por la ley de la esperanza total, el valor esperado puede tomarse primero sobre la pesca para un A_t dado; los otros factores dependen solo de A_t, y E[R_t | A_t] = q_*(A_t), así que el resultado es el mismo.
4. La pendiente del softmax. En π_t(x) = e^H_t(x)/Σ_b e^H_t(b), subir H_t(a) agranda la suma, y también el numerador cuando x = a. Por la regla del cociente, la pendiente es π_t(a) − π_t(a)² para x = a y −π_t(x)π_t(a) para cualquier otro x; en una sola fórmula, ∂π_t(x)/∂H_t(a) = π_t(x)(𝟙_a=x − π_t(a)), donde 𝟙_a=x vale 1 si a = x y 0 si no. El π_t(A_t) se cancela:
   ∂E[R_t]∂H_t(a) = E[(R_t − R_t)(𝟙_a=At − π_t(a))]

Una muestra de esta esperanza en lugar de la pendiente da

la actualización de las preferencias en una línea. Con a = A_t la indicadora vale 1, lo que da la primera línea de la actualización de arriba, y para cualquier otro a vale 0, lo que da la segunda. Usar una muestra, correcta solo en promedio, en lugar de la pendiente exacta es lo que hace estocástico el ascenso. El baseline no cambia la actualización esperada, sea cual sea su valor, siempre que no dependa del lugar elegido, pero sí cambia cuánto varían las actualizaciones individuales, y con ello cuán rápido se asientan las preferencias.

6Resumen

Las ideas clave junto a sus equivalentes en NumPy. r guarda la pesca de esta mañana y a su lugar, r_hist y a_hist las anteriores, r_a las pescas del lugar a hasta ahora, de la más antigua a la más reciente y con la de esta mañana incluida, q, n y h las estimaciones, los conteos y las preferencias, k el número de lugares y rng un generador aleatorio de NumPy.