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

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

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

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.

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

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