Tema

Bandidos de varios brazos

Aprendizaje por refuerzo
Nivel base
Con simulador interactivo

Un problema de bandidos de varios brazos plantea la elección repetida entre acciones de recompensa desconocida sin estados, y obliga a equilibrar la explotación de la mejor conocida con la exploración de las demás.

Nombre en inglés

Multi armed bandits

Intuición

Es el aprendizaje por refuerzo reducido a su núcleo, sin transiciones ni horizonte, de modo que todo lo que queda es el dilema entre aprovechar y averiguar. La medida natural no es la recompensa acumulada sino el arrepentimiento, es decir, lo que se dejó de ganar frente a quien conociera de antemano el mejor brazo. Las estrategias buenas exploran mucho al principio y cada vez menos, ya que la incertidumbre baja con el número de tiradas.

Fórmula

Q_{n+1} = Q_n + \frac{1}{n}(R_n - Q_n) \qquad \mathrm{UCB}_i = Q_i + c \sqrt{\frac{\ln t}{n_i}}

Ejemplo resuelto

Sean tres brazos. El primero se tiró dos veces con recompensas 1 y 0, de modo que su media vale 0.5; el segundo se tiró una vez con recompensa 1 y su media vale 1; el tercero no se tiró nunca. La estrategia voraz elegiría el segundo para siempre y nunca descubriría el tercero. Con una probabilidad de exploración de 0.1, nueve de cada diez veces elige el segundo y una de cada diez sortea entre los tres. La cota superior de confianza con constante 1, en el instante de decidir la cuarta tirada, da para el primero 0.5 más la raíz de 1.386 dividido entre 2, cerca de 1.333, y para el segundo 1 más la raíz de 1.386, cerca de 2.177; el tercero, sin tiradas, recibe prioridad absoluta. Si se tira el primero y sale 1, su media pasa a 0.5 más un tercio de 0.5, cerca de 0.667.

Errores frecuentes

Inicializar las medias en cero cuando las recompensas son positivas, lo que desalienta la exploración; los valores iniciales optimistas la fomentan sin coste añadido.
Mantener fija para siempre la probabilidad de exploración, con lo que el arrepentimiento crece de forma lineal en vez de logarítmica.
Comparar estrategias por la recompensa de una sola corrida, cuando la varianza entre corridas es alta y hace falta promediar muchas.

Ejercicio

Un brazo tiene media estimada 2 tras 4 tiradas y la quinta entrega 7. ¿Cuál es la media nueva con la actualización incremental?

Ver la solución

La actualización suma un quinto de la diferencia entre la recompensa y la media, es decir, 7 menos 2 dividido entre 5, que vale 1. La media nueva es 2 más 1 = 3, que coincide con el promedio directo de las cinco tiradas.