UCB2 para un problema Bandido Multibrazo (Multi-Armed Bandit)

En la entrega anterior de esta serie hemos comenzado a ver cómo aplicar los métodos UCB (Upper Confidence Bounds) para resolver un problema del Bandido Multibrazo. Métodos en los que se estima un límite de confiaban superior para la recompensa de cada uno de los bandidos. Seleccionando en cada momento el que tenga la recompensa media más el límite de confianza mayor. En esta ocasión vamos a ver cómo se puede implementar el método UCB2 para un problema Bandido Multibrazo.

El método UCB2 es una mejora de UCB1 en la que se reduce el número de veces en las que se selecciona un bandido que no sea el óptimo. Reduciendo de este modo el número de tiradas en modo exploración. Aunque esto se hace a costa de un algoritmo algo más complejo.

En UCB2 se selecciona el bandido que maximice el siguiente valor

X_{UCB2_j} = \bar{X_j} + \sqrt{\frac{(1 + \alpha) \log(\frac{e N}{\tau_j})}{2 \tau_j}},

Donde \bar{X_j} es la recompensa media observada en el bandido j, \alpha es un parámetro que se influye en el ratio de aprendizaje del algoritmo, N es el número total de tiradas en los todos los bandidos y \tau es un valor entero que se obtiene mediante la expresión

\tau_j = \lceil (1 + \alpha)^n_j \rceil.

Expresión en la que n_j es el número de veces que se ha realizado una tirada con el bandido j.

En UCB2 la fase de exploración se divide en épocas de tamaño variable en las que se juega con cada uno de los bandidos la siguiente cantidad de veces

\lceil (1 + \alpha)^{n_j+1} - (1 + \alpha)^n_j \rceil

Implementación de UCB2 en Python

Ahora que conocemos la expresión que se utiliza en UCB2 podemos implementar una clase en Python. Basándonos para ello en la creada anteriormente para UCB1. Clase a la que es necesario agregar una nueva propiedad para indicar el valor del parámetro alpha requerido por UCB2. Además es necesario modificar el método select() con las expresiones que se han visto anteriormente. Todo ello es lo que se muestra en el siguiente código.

import sys

class UCB2(Epsilon):
    def __init__(self, bandits, alpha=0.1):
        self.bandits = bandits
        self.alpha = alpha
        
        self.reset()
    
    
    def select(self):
        num_bandits = len(self.bandits)
        total = len(self._rewards)
        
        if total == 0:
            bandit = np.random.choice(len(bandits))
        else:
            ucb = [0] * num_bandits
            
            for i in range(num_bandits):
                try:
                    tau = int(np.ceil((1 + self.alpha) ** self._plays[i]))
                    if np.log(np.e * total / tau) > 0:
                        bonus = np.sqrt((1. + self.alpha) * np.log(np.e * total / tau) / (2 * tau))
                    else:
                        bonus = 0
                except:
                    bonus = 0
                    
                if np.isnan(bonus):
                    ucb[i] = self._mean[i] 
                else:
                    ucb[i] = self._mean[i] + bonus
        
            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)

Nótese que en el método select() la primera vez, cuando el número total de jugadas es cero, se selecciona un bandido de forma aleatoria. A partir de este punto se calcula un bonus para cada uno de los bandidos basado en el número de total de tiradas y las veces jugadas con cada uno de ellos.

Al igual que en ocasiones anteriores, cuando se observa un empate, se decide el bandido con el que se juega de forma aleatoria.

Resultados de UCB2

Para evaluar el rendimiento de este algoritmo se puede usar la clase Bandit con la que se han probado los algoritmos anteriores. Para ello solamente es necesario emplear el siguiente código:

np.random.seed(0)

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

ucb_a = UCB2(bandits, 0.5)
ucb_b = UCB2(bandits, 0.3)
ucb_c = UCB2(bandits, 0.1)

ucb_a.run(200000)
ucb_b.run(200000)
ucb_c.run(200000)

ucb_a.plot(True, label='0.5')
ucb_b.plot(True, label='0.3')
ucb_c.plot(True, True, label='0.1')
plt.legend()

Obteniendo como resultado la siguiente gráfica.

Evolución de la recompensa promedio con el número de tiradas para tres versiones del algoritmo UCB2 con tres bandidos basados en una distribución binomial

En esta ocasión lo primero que se puede apreciar es cómo la recompensa promedio después de 10.000 tiradas es prácticamente la óptima en todos los casos. Aunque, a medida que se aumenta el valor de alpha, vemos que el agente se decanta más rápidamente por la solución óptima. Lo que se puede ver en el número de veces totales que el agente ha jugado con soluciones sub-óptimas. En el caso de alpha igual a 0,5, el agente ha seleccionado 16 veces el primer bandido y 24 el segundo, por lo que ha jugado 199.960 veces de 200.000 con el bandido óptimo. Por otro lado, cuando alpha es 0,1 el agente ha jugado 66 veces con el primer y segundo bandido, jugando 199.868 con el óptimo. Números que explican claramente los resultados vistos en la figura.

Conclusiones

En esta ocasión hemos visto cómo usar UCB2 para un problema Bandido Multibrazo. Un método que ha demostrado ser el más eficiente de los vistos hasta el momento, aunque esto sea a costa de una mayor complejidad que UCB1. En futuras entregas veremos otros métodos UCB-Normal o UCB-Tuned.

Imagen de Kanenori en Pixabay