Bandidos con múltiples brazos: la mejor solución de aprendizaje por refuerzo para su tarea

Los Multi-Armed Bandits (MAB) forman una piedra angular en el mundo del aprendizaje por refuerzo y ofrecen un mecanismo poderoso para negociar escenarios que requieren un equilibrio óptimo entre la exploración y la explotación. La exploración se refiere a probar opciones novedosas, mientras que la explotación significa apegarse a la mejor opción actual. En tales circunstancias, los MAB a menudo resultan ser una elección estelar debido a sus mecanismos de aprendizaje inteligentes.

Primero, desentrañemos el concepto detrás de los MAB. Imagine a un jugador rodeado por una variedad de máquinas tragamonedas, cada una conocida como un "bandido de un solo brazo". Las decisiones críticas a tomar aquí implican determinar qué máquinas jugar, el orden de juego y la frecuencia de juego. El problema es que cada máquina ofrece una recompensa diferente e incierta. El objetivo final es acumular la recompensa acumulativa más alta en una secuencia de jugadas.

¿Qué es un Bandido de Armas Múltiples?

El nombre "bandido de múltiples brazos" proviene de un experimento mental que involucra a un jugador en una fila de máquinas tragamonedas (a menudo conocido como "bandidos de un solo brazo"). El jugador debe decidir en qué máquinas jugar, cuántas veces jugar en cada máquina y en qué orden, con el objetivo de maximizar su recompensa total.

En una definición más formal, un problema MAB es una tupla (A, R)

El objetivo del problema MAB es encontrar una política π (un mapeo de datos históricos a acciones) que maximice la recompensa total esperada Q durante un número determinado de rondas.

El dilema clave en MAB es el compromiso entre "exploración" y "explotación":

1. La exploración implica probar diferentes armas para aprender más acerca de la recompensa que podrían generar. Esto podría implicar tirar de brazos subóptimos, pero ayuda a recopilar información sobre el sistema.
2. La explotación implica tirar del brazo que el agente cree actualmente que tiene la mayor recompensa esperada, según la información que ha recopilado hasta el momento.

Equilibrar la exploración y la explotación es un desafío central en el aprendizaje por refuerzo y los problemas MAB.

Para abordar este problema, se han desarrollado una gran cantidad de algoritmos, incluidas las estrategias Epsilon-Greedy, Upper Confidence Bound (UCB) y Thompson Sampling.

La revisión detallada de Contextual Bandits como extensión del MAB se tratará en próximos artículos.

El Epsilon(ε)-Codicioso

La estrategia Epsilon(ε)-Greedy se adhiere a un principio sencillo. La mayoría de las veces, cuantificada como (1 - ε), opta por la acción que produce la mayor recompensa estimada, explotando así la opción más conocida. Sin embargo, el resto del tiempo, cuantificado como ε, elige una acción aleatoria, explorando así nuevas posibilidades. El ingenio de esta estrategia radica en su simplicidad y efectividad, a pesar de la advertencia de que podría seleccionar acciones menos gratificantes con la misma probabilidad que las más gratificantes durante su fase de exploración y el valor de ε determina el equilibrio entre exploración y explotación.

Matemáticamente se puede definir como:

Esto se puede definir mediante el siguiente pseudocódigo:

 Initialize Q(a) for all a Repeat: Generate a random number p between 0 and 1 If p < epsilon: Select a random action a Else: Select action a with the highest Q(a) Execute action a and observe reward r Update Q(a) = Q(a) + alpha * (r - Q(a))

La implementación Pythonic de la estrategia Epsilon-Greedy es bastante sencilla:

 import numpy as np class EpsilonGreedy: def __init__(self, epsilon, counts, values): self.epsilon = epsilon self.counts = counts self.values = values def select_arm(self): if np.random.random() < self.epsilon: return np.random.choice(len(self.values)) else: return np.argmax(self.values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

El algoritmo ε-voraz tiene el beneficio de la simplicidad y la garantía de que continuará explorando (un poco) incluso después de muchos pasos. Sin embargo, no tiene en cuenta cuánto se sabe sobre cada acción cuando explora, a diferencia de UCB o Thompson Sampling.

UCB

Por el contrario, la estrategia UCB tiene en cuenta tanto la recompensa estimada como la incertidumbre o varianza asociada al decidir una acción. Exhibe preferencia por acciones con alta incertidumbre, buscando disminuirla y asegurando una fase de exploración más productiva. La estrategia UCB se define matemáticamente de la siguiente manera:

Su implementación en Python es la siguiente:

 class UCB: def __init__(self, counts, values): self.counts = counts self.values = values def select_arm(self): n_arms = len(self.counts) for arm in range(n_arms): if self.counts[arm] == 0: return arm ucb_values = [0.0 for arm in range(n_arms)] total_counts = sum(self.counts) for arm in range(n_arms): bonus = sqrt((2 * log(total_counts)) / float(self.counts[arm])) ucb_values[arm] = self.values[arm] + bonus return np.argmax(ucb_values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

El equilibrio entre exploración y explotación en UCB proviene de su fórmula: el valor estimado de una acción más un término que disminuye con el tiempo (a medida que se aprende más sobre la acción) pero aumenta con la incertidumbre sobre esa acción. Por lo tanto, el algoritmo tiende a explorar armas con alta incertidumbre y alta recompensa potencial.

Muestreo de Thompson

Thompson Sampling es un algoritmo de inspiración bayesiana para el problema del bandido con múltiples brazos. Asigna una distribución previa a las probabilidades de recompensa de cada bandido (o cada acción), luego actualiza estas distribuciones previas a medida que se observan las recompensas. La selección de acciones es probabilística, según la distribución posterior sobre la mejor acción.

En un marco Beta-Bernoulli, consideramos la distribución de recompensas de cada bandido como una distribución de Bernoulli (es decir, recompensas binarias 0 o 1). Luego asignamos una Beta antes de la probabilidad de obtener una recompensa. La distribución Beta es la anterior conjugada de la distribución de Bernoulli, lo que permite una fácil actualización posterior.

Lógica:

1. Asigne a cada bandido una distribución Beta con parámetros α=1, β=1 (Uniforme antes).

2. Para cada ronda:

   1. Muestra un número aleatorio de la distribución Beta actual de cada bandido.
   2. Seleccione el bandido con el número muestreado más alto y tire de ese bandido.
   3. Observe la recompensa del bandido tirado. Si tiene éxito (1), aumenta el α del bandido en uno; si es un fracaso (0), aumenta el β del bandido en uno.
   4. Repita los pasos 2 y 3.

 import numpy as np from scipy.stats import beta class Bandit: def __init__(self, true_probability): self.true_probability = true_probability self.alpha = 1 self.beta = 1 def pull(self): return np.random.random() < self.true_probability def sample(self): return np.random.beta(self.alpha, self.beta) def update(self, reward): self.alpha += reward self.beta += (1 - reward) def Thompson(bandits, num_trials): rewards = np.zeros(num_trials) for i in range(num_trials): # Thompson sampling j = np.argmax([b.sample() for b in bandits]) # Pull the arm for the bandit with the largest sample reward = bandits[j].pull() # Update rewards log rewards[i] = reward # Update the distribution for the bandit whose arm we just pulled bandits[j].update(reward) return rewards # Suppose we have 3 bandits with these true probabilities true_probabilities = [0.2, 0.5, 0.75] bandits = [Bandit(p) for p in true_probabilities] # Run experiment rewards = Thompson(bandits, num_trials=10000) # Print the total reward print("Total reward earned:", rewards.sum()) print("Overall win rate:", rewards.sum() / len(rewards))

Por lo tanto, Thompson Sampling "explora" acciones sobre las que no está seguro (aquellas para las que la distribución de valores está dispersa) y "explota" acciones que cree que pueden tener un alto valor (aquellas para las que la distribución está sesgada hacia valores altos).

Con el tiempo, a medida que se aprende más sobre cada acción, las distribuciones alcanzan un máximo y las acciones elegidas por el algoritmo tienden a converger en la que tiene el valor esperado más alto.

El equilibrio exploración/explotación en Thompson Sampling proviene naturalmente de la forma de las distribuciones. Este método es bastante efectivo, pero puede ser más complejo de implementar que UCB o ε-greedy, particularmente para problemas con espacios de acción grandes o continuos, o estructuras de recompensa complejas.

¿Por qué los Multi-Armed Bandits son los mejores RL para su tarea?

1. Simplicidad : los algoritmos MAB son más simples y computacionalmente más eficientes que los algoritmos RL completos, que requieren mantener y actualizar una tabla o aproximador de valores de acción de estado potencialmente grande.
2. Equilibrio de exploración y explotación : los algoritmos MAB proporcionan métodos sólidos para gestionar el equilibrio entre probar nuevas acciones y apegarse a las buenas acciones conocidas.
3. Adaptabilidad en tiempo real : los algoritmos MAB pueden adaptarse en tiempo real a los cambios en las distribuciones de recompensas de las acciones.
4. Fácil integración : la simplicidad y la eficiencia de los MAB permiten una fácil integración en los sistemas existentes, lo que brinda beneficios inmediatos con una interrupción mínima.
5. Amplia aplicabilidad : los MAB se han aplicado con éxito en diversos campos, incluida la publicidad (elegir qué anuncio mostrar para maximizar la tasa de clics), la atención médica (estrategias de tratamiento personalizadas) y la optimización de páginas web (pruebas A/B).

Aplicaciones de los MAB

Los Multi-Armed Bandits (MAB) tienen una amplia gama de aplicaciones en diversas industrias y dominios. Estos son algunos ejemplos de cómo se pueden utilizar:

1. Publicidad en línea : los MAB se pueden usar para ajustar dinámicamente la selección de anuncios para mostrar a los usuarios en función de sus interacciones. Esto ayuda a maximizar las tasas de clics o las conversiones a lo largo del tiempo.
2. Ensayos clínicos : en la investigación médica, los algoritmos MAB se pueden usar para asignar dinámicamente a los pacientes a diferentes tratamientos. Esto asegura que más pacientes reciban los tratamientos más efectivos, reduciendo así el arrepentimiento, es decir, la pérdida en la que se incurre por no elegir siempre el mejor tratamiento.
3. Recomendación de artículos de noticias : los sitios web de noticias pueden usar MAB para personalizar los artículos que se muestran a cada usuario. El algoritmo MAB puede aprender con el tiempo qué tipos de artículos le interesan a cada usuario y ajustar las recomendaciones en consecuencia.
4. Precios dinámicos : las plataformas de comercio electrónico o las aerolíneas pueden usar algoritmos MAB para optimizar sus estrategias de precios en tiempo real, maximizando los ingresos en función del comportamiento del cliente y la dinámica del mercado.
5. Enrutamiento de red : en las redes informáticas, los algoritmos MAB se pueden utilizar para gestionar la congestión y optimizar el enrutamiento de paquetes. Cada ruta se puede tratar como un brazo y el algoritmo puede seleccionar rutas dinámicamente para minimizar la pérdida de paquetes o la latencia.
6. Ajuste de hiperparámetros de aprendizaje automático : los MAB también se pueden utilizar para optimizar la selección de hiperparámetros en modelos de aprendizaje automático. Cada conjunto de hiperparámetros se puede tratar como un brazo, y el algoritmo puede refinar iterativamente la selección para encontrar la configuración de modelo óptima.

En esencia, la utilidad de los MAB se extiende mucho más allá de las tareas de aprendizaje por refuerzo convencionales. Simbolizan un marco efectivo para mejorar los procesos de toma de decisiones en entornos de incertidumbre, brindando soluciones prácticas a problemas del mundo real en varios dominios. Por lo tanto, cuando la tarea en cuestión implica equilibrar la exploración y la explotación, los MAB a menudo surgen como la opción de acceso, proporcionando una solución versátil, sólida y adaptable a los enigmas de la toma de decisiones.

Conclusión

Multi-Armed Bandits, con su capacidad para equilibrar la exploración y la explotación de manera efectiva, brindan una solución sólida a muchos problemas de toma de decisiones del mundo real. Su adaptabilidad y versatilidad inherentes los convierten en una herramienta valiosa, no solo en el ámbito del aprendizaje por refuerzo, sino también en una amplia gama de aplicaciones, desde la atención médica hasta la publicidad en línea. Tanto si es un científico de datos, un entusiasta del aprendizaje automático o un profesional que busca mejorar sus procesos de toma de decisiones, comprender e implementar las estrategias MAB puede ser una experiencia enriquecedora y gratificante.