El Bandido Multibrazo (Multi-Armed Bandit)

El bandido multibrazo (multi-armed bandit) es uno de los problemas clásicos del aprendizaje por refuerzo. En este problema a un agente se le ofrece la posibilidad de jugar con N máquinas tragaperras, a las que se les suele llamar "bandidos" o "brazos", que ofrecen diferentes recompensas. La recompensa que ofrece cada uno de los bandidos viene dada por una distribución de probabilidad que es diferente. Distribución que el agente no conoce a priori. El objetivo es maximizar el beneficio obtenido después de jugar una cantidad dada fijada de antemano. Esto es, descubrir el bandido que ofrece la recompensa promedio mayor en el menor número de jugadas. Para, de este modo, maximizar el beneficio jugando la mayor cantidad de veces posible únicamente con este bandido.

Exploración frente a explotación

El problema de identificar el mejor bandido es un problema más complejo de lo que parece al principio. Dado que la recompensa viene dada por una distribución de probabilidad, es posible que uno de los peores agentes de grandes recompensas en las primeras jugadas. De forma análoga, el mejor bandido puede que no obtenga ningún premio en las primeras tiradas. Por los que si el agente no realiza las suficientes tiradas de prueba es posible que se decante por un bandido que no sea el óptimo. En el lado opuesto se encuentra el problema de jugar demasiado veces con un bandido no óptimo en la fase de exploración. Siendo esto lo que se conoce como el dilema Exploración frente a Explotación (Exploration vs. Exploitation). Esto es, cuando debemos parar de explorar para explotar el conocimiento adquirido.

Rechazo acumulado

Ahora para jugar a este juego se ha de crear un algoritmo que seleccione con cuál de los bandidos debe jugar en cada tirada y medir su éxito. Para lo que se puede definir una métrica que sea la diferencia entre la recompensa máxima que se podría obtener y la obtenida realmente, a la que se conoce con el nombre de rechazo acumulado (cumulative regret).

El valor de esta métrica es cero si el algoritmo empleado selecciona siempre el mejor bandido. Aumentado el valor a medida que el algoritmo juegue con los bandidos que no son óptimos.

El rechazo acumulado es un indicador que en un caso real es difícil de calcular, ya que solamente se observa la recompensa obtenida. No observándose la recompensa de los bandidos en los que no se ha jugado. Por eso es más habitual utilizar en su lugar el pseudo rechazo (pseudo regret) que es la diferencia entre la recompensa esperada para el mejor bandido frente a la esperada por el algoritmo.

Es importante notar que el valor del pseudo rechazo es inferior al valor del rechazo acumulado. Ya que el pseudo rechazo compara el resultado con el mejor bandido en general, mientras que el rechazo acumulado lo hace con el mejor bandido para cada una de las jugadas.

Conclusiones

En esta ocasión hemos visto un problema clásico de aprendizaje por refuerzo: el bandido multibrazo (multi-armed bandit). Un problema que veremos en futuras entradas diferentes estrategias para resolver. Estrategias basadas en fundamentos estadísticos como puede ser una prueba A/B o basados en diferentes estrategias como pueden se Epsilon-greedy, valores iniciales optimistas, UCB1 o Bayes.

Imagen de Aidan Howe en Pixabay