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

La familia de algoritmos UCB es una de las que mejores resultados producen a la hora de enfrentarse a problemas tipo bandido multibrazo. En la que en bandido se selecciona teniendo en cuenta el intervalo de confianza de la recompensa empírica. Así no se selecciona el bandido cuya recompensa observada sea la mayor, sino aquel en el que estadísticamente se puede esperar el máximo valor para un nivel de confianza dado sea el mayor. Permitiendo explorar de este modo los estados con un nivel de incertidumbre elevado y explotar aquellos con mayor esperanza. Entre esta familia de algoritmos se encuentra el UCB de Clopper-Pearson (CP-UCB) en el cual se asume que la recompensa se genera mediante una distribución binomial.

CP-UCB

El algoritmo CP-UCB propone asumir que las recompensas obtenidas provienen de una distribución binomial. Así, a partir de los datos empíricos, se puede calcular para cada uno de los bandidos su intervalo de confianza para un nivel de significancia dada. Nivel de significación que se reducirá a medida que aumente el número de muestras.

En donde U^{CP} es la función que nos calcular el intervalo de confianza de una distribución binomial, R_j las recompensas totales observadas en en bandido j, n_j las veces que se ha jugado con el bandido j, N el número de veces totales que se ha jugado y c un parámetro que se puede seleccionar para cambiar la velocidad de aprendizaje.

Implementación en Python de CP-UCB

Para implementar CP-UCB necesitamos una función con la que se puede calcular el intervalo de confianza de una distribución binomial. Una función como proportion_confint la cual se puede encontrar en el paquete statsmodels.

Una vez que tenemos la función con la que calcular el intervalo de confianza, como en ocasiones anteriores, nos podemos basar en la clase Epsilon implementada en la entrada de valores iniciales optimistas. Para ello solamente hay que crear una clase hija con el siguiente código.

from statsmodels.stats.proportion import proportion_confint

class CPUCB(Epsilon):
    def __init__(self, bandits, c=1, method='beta'):
        self.bandits = bandits
        self.c = c
        self.method = method
        
        self.reset()
        
    def run(self, episodes=1):
        for i in range(episodes):
            # Selección del bandido
            bandit = self.select()
            
            # Obtención de una nueva recompensa
            reward = bandits[bandit].pull()
            
            # Agregación de la recompensa al listado
            self._rewards.append(reward)
            
            # Actualización de la media
            self._plays[bandit] += 1
            self._mean[bandit] = (1 - 1.0/self._plays[bandit]) * self._mean[bandit] \
                                 + 1.0/self._plays[bandit] * reward
            self._reward[bandit] += reward
        
        return self.average_reward()
    
    
    def select(self):
        num_bandits = len(self.bandits)
        total = len(self._rewards)
        
        if total < num_bandits:
            bandit = total
        else:
            ucb = [0] * num_bandits
                
            for i in range(num_bandits):
                confidence = 1 / (total * np.log(total) ** self.c)
                ucb[i] = proportion_confint(self._reward[i], self._plays[i], confidence, method=self.method)[1]            
            
            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)
        self._reward = [0] * len(self.bandits)

En este caso ha sido necesario cambiar el método run() ya que, además de los valores usados anteriormente, es necesario guardar también la recompensa obtenida. Valor que se guarda en la propiedad privada _reward. Por otro lado, también se ha modificado el método select(), usando la función proportion_confint para calcular el valor usado para seleccionar el bandido. Finalmente, en el método reset() de la clase hay que agregar la inicialización de la propiedad _reward.

Evaluación de los resultados de CP-UCB

Una vez implementado el algoritmo se puede ver cómo funciona este en comparación con UCB1. Para lo que se puede usar los bandidos basados en la distribución binomial de las entradas anteriores. Así, se puede usar el siguiente código para evaluar ambos algoritmos.

np.random.seed(0)

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

cpucb = CPUCB(bandits)
ucb1 = UCB1(bandits)

cpucb.run(200000)
ucb1.run(200000)

cpucb.plot(True, label='CPUCB')
ucb1.plot(True, True, label='UCB1')
plt.legend()

print(cpucb._plays)
print(ucb1._plays)

Obteniendo como resultado la siguiente figura.

Lo primero que se puede ver en esta gráfica es que CP-UCB converge mucho más rápido hacia la recompensa óptima que UCB1. Algo que queda de manifiesto al comprobar que solamente ha jugado con el primer y segundo bandido 169 y 1263 veces respectivamente. Sumando ambas menos que las veces que UCB1 ha jugado con el primer bandido (3089). Lo que se traduce en haber seleccionado muchas más veces el bandido óptimo.

Este resultado tiene un precio. El uso de la función proportion_confint en cada una de las selecciones hace que este algoritmo sea uno de los más lentos, tardando 10 veces más que UCB2, UCB1-Tuned o UCB1-Normal.

En este caso el resultado es en cierta medida el esperado, ya que el bandido usa una distribución binomial para generar la recompensa. Por lo que el algoritmo se adapta perfectamente al problema.

Conclusiones

En esta entrada hemos visto otro algoritmo de la familia UCB en el que se asume que las recompensas de los bandidos proceden de una distribución binomial. Por lo que los resultados obtenidos en los bandidos de prueba han sido de los mejores. Algo que también tiene un coste, el cálculo de intervalo de confianza es más costosos que otros algoritmos de la familia, por lo que usar este se traduce en la necesidad de más tiempo para tomar las decisiones. Lo que puede ser un problema en algunas situaciones.

Imagen de Paul Edney en Pixabay