• Saltar al contenido principal
  • Skip to secondary menu
  • Saltar a la barra lateral principal
  • Saltar al pie de página
  • Inicio
  • Secciones
    • Ciencia de datos
    • Criptografía
    • Herramientas
    • Machine Learning
    • Noticias
    • Opinión
    • Productividad
    • Programación
      • JavaScript
      • Julia
      • Matlab
      • Python
      • R
  • Programación
    • JavaScript
    • Julia
    • Matlab
    • Python
    • R
  • Herramientas
    • Método D’Hondt – Atribución de escaños
  • Noticias
  • Boletín
  • Contacto
  • Tienda
    • Libros
    • Equipamiento de oficina
    • Equipamiento en movilidad
    • Tiendas afiliadas
      • AliExpress
      • Amazon
      • Banggood
      • GeekBuying
      • Lenovo

Analytics Lane

Ciencia e ingeniería de datos aplicada

  • Ciencia de datos
  • Machine Learning
  • Python
  • Pandas
  • NumPy
  • Matlab
  • Julia
  • Excel
  • IA Generativa

KL-UCB para un problema Bandido Multibrazo (Multi-Armed Bandit)

mayo 7, 2021 Por Daniel Rodríguez Deja un comentario
Tiempo de lectura: 4 minutos

Continuando con el repaso a los principales algoritmos existentes para abordar los problemas tipo Bandido Multibrazo (Multi-Armed Bandit) vamos a ver en esta ocasión KL-UCB. Una versión del UCB donde se utiliza la divergencia de Kullback-Leibler para seleccionar el mejor bandido óptimo en cada jugada.

La divergencia de Kullback-Leibler

Una de las medidas más populares para medir la diferencia entre dos distribuciones de probabilidad sobre la misma variable es la divergencia de Kullback-Leibler (KL). Una medida no simétrica estrechamente relacionada con la entropía relativa, la divergencia de la información y la ganancia de la información. En concreto, la divergencia KL de para dos distribuciones p(x) y q(x) es una media de la información pedida cuando se emplea q(x) para aproximar p(x). Un valor que, en el caso de una distribución de variable discreta se puede obtener mediante la expresión:

d_{KL} \left(p(x)|q(x)\right) = \sum_x p(x) \log \left|\frac{p(x)}{q(x)}\right|

Mientras que en el caso de distribuciones de una variable continua se emplearía

d_{KL} \left(p(x)|q(x)\right) = \int_{-\infty}^{\infty} p(x) \log \left|\frac{p(x)}{q(x)}\right| dx

Publicidad


KL-UCB

KL-UCB es un enfoque UCB (Upper Confidence Bound) para resolver el problema del bandido multibrazo donde la función para seleccionar al bandido se deriva de la divergencia KL. Un algoritmo en el que se considera la distancia entre las distribuciones estimadas para cada uno de los bandidos. En el caso de bandidos basados en la distribución de Bernoulli la divergencia KL se puede obtener mediante la expresión

Consistencia en nombres y orden en TypeScript: la base de un código mantenible aplicado a tslane
En Analytics Lane
Consistencia en nombres y orden en TypeScript: la base de un código mantenible aplicado a tslane

d_{KL}(p,q) = p \log\frac{p}{q} + (1 - p) \log\frac{1-p}{1-q}

Algo que se puede extender fácilmente al caso de distribuciones binomiales como las que usan los bandidos implementados en entrada anteriores, para lo que simplemente se debe multiplicar el valor anterior por el número de intentos

d_{KL}(p,q,n) = n \left( p \log\frac{p}{q} + (1 - p) \log\frac{1-p}{1-q} \right)

Ahora para seleccionar un bandido en cada una de las jugadas se busca el valor que maximice la siguiente expresión

j = \arg \max_j (n_j d_{KL}(\bar{X_j}, M \le \log N + c \log\log N)

Donde n_j es el número de veces que se ha jugado con el bandido j, N es el número total de veces que se ha jugado y c es un parámetro.

Implementación de KL-UCB en Python

Para facilitar la implementación de KL-UCB en Python se puede partir de la clase Epsilon implementada previamente en Epsilon-Greedy con decaimiento. A partir de la cual se puede crear una clase hija en la que se sobreescriba el método select() con KL-UCB. Pudiéndose agregar dos nuevas propiedades para configurar el número de pruebas de la distribución binomial (n) y el hiperparámetro c. Además de esto, en este caso también es necesario definir una función en la que se implemente la divergencia KL. Lo que se muestra en el siguiente código.

def klBin(p, q, n=1, eps=1e-15):
    p = min(max(p, eps), 1 - eps)
    q = min(max(q, eps), 1 - eps)
    
    return n * (p * np.log(p / q) + (1 - p) * np.log((1 - p) / (1 - q)))

class KLUCB(Epsilon):
    def __init__(self, bandits, n=1, c=0):
        self.bandits = bandits
        self.n = 1
        self.c = 1
        
        self.reset()
        
    
    def select(self):
        num_bandits = len(self.bandits)
        total = len(self._rewards)
        
        if total < num_bandits:
            bandit = total
        else:
            ucb = [0] * num_bandits
            d = np.log(total) + self.c * np.log((total + 1))
                
            for i in range(num_bandits):
                ucb[i] = klBin(self._mean[i], d / self._plays[i], self.n)
        
            max_bandits = np.where(ucb == np.max(ucb))[0]
            bandit = np.random.choice(max_bandits)
            
        return bandit
    
    
    def reset(self, initial=None):
        self._rewards = []
        self._plays = [0] * len(self.bandits)
        self._mean = [0] * len(self.bandits)

Antes de poder aplicar el algoritmo para seleccionar el bandido es necesario que, por lo menos, exista una tirada con cada uno de los bandidos. Debido a esto en el método select() las primeras jugadas son con cada uno de los bandidos definidos. A partir de ese punto, el bandido se selecciona usando la divergencia KL. Para lo que primero se calcula el valor de d que posteriormente se divide por el número de veces que se ha jugado con cada uno de los bandidos.

En el caso de la función klBin se evita explícitamente usar 0 o 1 en los valores de p y q para evitar logaritmos y divisiones por cero. Motivo por el que se ha definido el parámetro eps.

Publicidad


Resultados

Una vez implementado el algoritmo se puede comparar el rendimiento de KL-UCB con UCB1 empleando para ello los bandidos basados en una distribución binomial. Para lo que se puede utilizar el siguiente código.

np.random.seed(0)

bandits = [Bandit(0.02), Bandit(0.06), Bandit(0.10)]

ucb_kl = KLUCB(bandits)
ucb_1 = UCB1(bandits)

ucb_kl.run(200000)
ucb_1.run(200000)

ucb_kl.plot(True, label='KL-UCB')
ucb_1.plot(True, True, label='UCB1')
plt.legend()

Con el que se obtiene la siguiente gráfica como resultado.

Evolución de la recompensa promedio con el número de tiradas para KL-UCB y UCB1 con tres bandidos basados en una distribución binomial
Evolución de la recompensa promedio con el número de tiradas para KL-UCB y UCB1 con tres bandidos basados en una distribución binomial

En este ejemplo se puede ver que el resultado de KL-UCB converge más rápidamente que UCB-1. Aunque la implementación de KL-UCB puede presentar problemas de estabilidad en el caso de que en las primeras tiradas se obtenga muy buenos resultados en bandidos que no sea el óptimo. Lo que puede llevar a que el valor de la divergencia KL sea cero para ellos, algo que se puede evitar aumentando el número de jugadas fijas con cada uno de los bandidos.

Conclusiones

En esta ocasión hemos visto un nuevo algoritmo para solucionar un problema tipo Bandido Multibrazo, el método KL-UCB. Un método que viene a completar los ya vistos como Epsilon-Greedy, UCB1, UCB2, UCB1-Tuned, UCB1-Normal y BayesUCB.

Imagen de max_gloin en Pixabay

¿Te ha parecido de utilidad el contenido?

¡Puntúalo entre una y cinco estrellas!

Puntuación promedio 0 / 5. Votos emitidos: 0

Ya que has encontrado útil este contenido...

¡Síguenos en redes sociales!

¡Siento que este contenido no te haya sido útil!

¡Déjame mejorar este contenido!

Dime, ¿cómo puedo mejorar este contenido?

Publicidad


Publicaciones relacionadas

  • Consistencia en nombres y orden en TypeScript: la base de un código mantenible aplicado a tslane
  • Análisis de Redes con Python
  • Nuevo calendario de publicaciones: más calidad, mejor ritmo
  • Probabilidad básica: cómo entender el azar en nuestra vida diaria
  • Cómo eliminar las noticias en Windows 11 y recuperar tu concentración
  • Publicaciones de verano 2025: los trucos más populares, ahora en vídeo
  • Cómo enviar correos desde PowerShell utilizando Brevo: Guía paso a paso para automatizar tus notificaciones
  • Nueva herramienta disponible: Calculadora del Método D’Hondt para la atribución de escaños
  • Cómo enviar correos desde Python utilizando Brevo: Automatiza tus notificaciones con scripts eficientes

Publicado en: Ciencia de datos Etiquetado como: Aprendizaje por refuerzo, Machine learning, Multi-Armed Bandit

Interacciones con los lectores

Deja una respuesta Cancelar la respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

I accept the Terms and Conditions and the Privacy Policy

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

Barra lateral principal

Suscríbete a nuestro boletín

Suscríbete al boletín semanal para estar al día de todas las publicaciones.

Política de Privacidad

Analytics Lane en redes sociales

  • Amazon
  • Bluesky
  • Facebook
  • GitHub
  • Instagram
  • Mastodon
  • Pinterest
  • RSS
  • Telegram
  • Tumblr
  • Twitter
  • YouTube

Publicidad

Entradas recientes

¡Nuevo video! Gráficos de barras en Matplotlib sin complicarte

julio 17, 2025 Por Daniel Rodríguez

¡Nuevo video! Iterar filas en Pandas sin romperte la cabeza

julio 15, 2025 Por Daniel Rodríguez

¡Nuevo video! Encuentra la posición en listas como un PRO

julio 10, 2025 Por Daniel Rodríguez

Publicidad

Es tendencia

  • Obtención de valores únicos de una columna con Pandas publicado el mayo 8, 2019 | en Python
  • Cómo encontrar la posición de elementos en una lista de Python publicado el abril 12, 2021 | en Python
  • Solución al error Failed to download metadata for repo ‘AppStream’ en CentOS 8 publicado el septiembre 13, 2023 | en Herramientas
  • Combinar varios archivos Jupyter Notebook en uno publicado el noviembre 21, 2022 | en Python
  • Sistema de ecuaciones Sistemas de ecuaciones lineales con numpy publicado el octubre 29, 2018 | en Python

Publicidad

Lo mejor valorado

4.9 (24)

Seleccionar filas y columnas en Pandas con iloc y loc

4.6 (16)

Archivos JSON con Python: lectura y escritura

4.4 (14)

Ordenación de diccionarios en Python mediante clave o valor

4.7 (13)

Operaciones de filtrado de DataFrame con Pandas en base a los valores de las columnas

4.5 (10)

Diferencias entre var y let en JavaScript

Publicidad

Comentarios recientes

  • Piera en Ecuaciones multilínea en Markdown
  • Daniel Rodríguez en Tutorial de Mypy para Principiantes
  • Javier en Tutorial de Mypy para Principiantes
  • javier en Problemas con listas mutables en Python: Cómo evitar efectos inesperados
  • soldado en Numpy básico: encontrar la posición de un elemento en un Array de Numpy

Publicidad


Footer

Analytics Lane

  • Acerca de Analytics Lane
  • Boletín de noticias
  • Contacto
  • Libros
  • Lo más popular
  • Noticias
  • Tienda
  • Tiendas afiliadas

Secciones

  • Ciencia de datos
  • Criptografía
  • Herramientas
  • Machine Learning
  • Opinión
  • Productividad
  • Programación
  • Reseñas

Sobre de Analytics Lane

En Analytics Lane tratamos de explicar los principales conceptos de la ciencia e ingeniería de datos con un enfoque práctico. Los principales temas tratados son ciencia de datos, ingeniería de datos, inteligencia artificial, machine learning, deep learning y criptografía. Además, también se habla de los principales lenguajes de programación y herramientas utilizadas por los científicos e ingenieros de datos.

Copyright © 2018-2025 Analytics Lane ·Términos y condiciones ·Política de Cookies ·Política de Privacidad ·Herramientas de privacidad ·Contacto