intro_bandit.ipynb

Kernel: Python 3

Copyright 2023 The TF-Agents Authors.

#@title Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

Introducción a los bandidos multibrazo

Ver en TensorFlow.org

Ejecutar en Google Colab

Ver código fuente en GitHub

Descargar bloc de notas

Introducción

El bandido multibrazo (MAB) es un marco de aprendizaje automático en el que un agente debe seleccionar acciones (brazos) para maximizar su recompensa acumulada a largo plazo. En cada ronda, el agente recibe información sobre el estado actual (contexto), luego elige una acción con base en esta información y la experiencia adquirida en rondas anteriores. Al final de cada ronda, el agente recibe la recompensa asociada a la acción elegida.

Quizás el mejor ejemplo sea el problema que dio nombre al MAB: imaginemos que estamos ante k máquinas tragamonedas (bandidos de un brazo) y tenemos que averiguar cuál paga mejor, sin perder demasiado dinero.

Probar una vez cada máquina y luego elegir la que pagó mejor no sería la mejor estrategia: el agente podría acabar eligiendo una máquina que tuvo un resultado favorable al principio, pero que no es óptima en términos generales. En lugar de eso, el agente debería volver repetidamente a elegir máquinas que no parezcan tan buenas, para recopilar más información sobre ellas. Este es el principal reto de los bandidos multibrazo: el agente tiene que encontrar la combinación adecuada entre la explotación del conocimiento previo y la exploración para no pasar por alto las acciones óptimas.

Los casos más prácticos de MAB incluyen un dato secundario cada vez que el aprendiz toma una decisión. A esta información secundaria la llamamos "contexto" u "observación".

Bandidos multibrazo y aprendizaje por refuerzo

¿Por qué hay un paquete MAB en la biblioteca de TF-Agents? ¿Cuál es la conexión entre RL y MAB? Los Bandidos Multibrazo pueden considerarse un caso especial del Aprendizaje por Refuerzo. Como dice en Introducción al RL:

En cada paso de tiempo, el agente toma una acción en el entorno con base en su política $\pi(a_t|s_t)$, donde $s_t$ es la observación actual del entorno, y recibe una recompensa $r_{t+1}$ y la siguiente observación $s_{t+1}$ del entorno. El objetivo es mejorar la política para maximizar la suma de recompensas (rendimiento).

En el caso general del RL, la siguiente observación $s_{t+1}$ depende del estado anterior $s_t$ y de la acción $a_t$ adoptada por la política. Esta última parte es la que diferencia el MAB del RL: en el MAB, el siguiente estado, que es la observación, no depende de la acción elegida por el agente.

Esta similitud nos permite reutilizar todos los conceptos que existen en TF-Agents.

• Un entorno genera observaciones y responde a las acciones con recompensas.

• Una política genera una acción en función de una observación, y

• un agente actualiza reiteradamente la política en función de las tuplas observación-acción-recompensa anteriores.

El entorno de setas

A título ilustrativo, utilizamos un ejemplo de juguete denominado "Entorno de setas". El conjunto de datos de las setas (Schlimmer, 1981) consiste en ejemplos etiquetados de setas comestibles y venenosas. Las características incluyen formas, colores, tamaños de las distintas partes de la seta, además del olor y muchas más.

El conjunto de datos de setas, al igual que todos los conjuntos de datos de aprendizaje supervisado, se puede convertir en un problema MAB contextual. Aquí usamos el método utilizado también por Riquelme et al. (2018). En esta conversión, el agente recibe las características de una seta y decide si comerla o no. Comer una seta comestible da como resultado una recompensa de +5, mientras que comer una seta venenosa dará +5 o -35 con la misma probabilidad. No comer la seta da como resultado 0 de recompensa, independientemente del tipo de seta. La siguiente tabla resume la asignación de recompensas:

       | edible | poisonous

-----------|--------|---------- eating it | +5 | -35 / +5 leaving it | 0 | 0

El agente LinUCB

Desempeñarse bien en un entorno de bandido contextual requiere una buena estimación de la función de recompensa de cada acción, a partir de la observación. Otra posibilidad es estimar la función de recompensa con funciones lineales. Es decir, para cada acción $i$, tratamos de encontrar el parámetro $\theta_i\in\mathbb R^d$ para el que las estimaciones

$r_{t, i} \sim \langle v_t, \theta_i\rangle$

se aproximen lo más posible a la realidad. Aquí $v_t\in\mathbb R^d$ es el contexto recibido en el paso de tiempo $t$. Entonces, si el agente tiene mucha confianza en sus estimaciones, puede elegir $\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle$ para obtener la mayor recompensa esperada.

Como ya hemos explicado, elegir simplemente el brazo con la mejor recompensa estimada no supone una buena estrategia. Hay muchas maneras diferentes de mezclar la explotación y la exploración en los agentes de estimación lineal, y uno de los más famosos es el algoritmo Linear Upper Confidence Bound (LinUCB) (consulte, por ejemplo, Li et al. 2010). LinUCB tiene dos componentes principales (se omiten algunos detalles):

1. Mantiene estimaciones para los parámetros de cada brazo con mínimos cuadrados lineales: $\hat\theta_i\sim X^+_i r_i$, donde $X_i$ y $r_i$ son los contextos y las recompensas apilados de las rondas donde se elegía el brazo $i$, y $()^+$ es el pseudo inverso.

2. Mantiene elipsoides de confianza definidos por la covarianza inversa $X_i^\top X_i$ para las estimaciones anteriores.

La idea principal de LinUCB es la de "Optimismo ante la incertidumbre". El agente incorpora la exploración mediante el incremento de estimaciones en una cantidad que corresponde a la variación de esas estimaciones. Ahí es donde los elipsoides de confianza entran en juego: para cada brazo, la estimación optimista es $\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle$, donde $E_i$ es el elipsoide en torno a $\hat\theta_i$. El agente elige el brazo más atractivo $\arg\max_i\hat r_i$.

De más está decir que la anterior descripción no es más que un resumen intuitivo y superficial de lo que hace LinUCB. Se puede encontrar una implementación en nuestro código base aquí.

Siguientes pasos

Si desea acceder a un tutorial más detallado sobre nuestra biblioteca Bandits, consulte nuestro tutorial de Bandits. Si, en cambio, desea comenzar a explorar nuestra biblioteca de inmediato, puede encontrarla aquí. Si está aún más ansioso por comenzar a capacitarse, consulte algunos de nuestros ejemplos completos aquí, incluido el entorno de setas descrito anteriormente con LinUCB que puede encontrar aquí.