• 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
  • 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
  • JavaScript
  • Excel

Epsilon-Greedy con decaimiento para un problema Bandido Multibrazo (Multi-Armed Bandit)

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

La semana pasada vimos cómo se podía usar la estrategia Epsilon-Greedy para resolver un problema tipo bandido multibrazo. Una estrategia que nos había dado mejores resultados que un test A/B. Pero esta estrategia tiene un problema, una vez que se sabe cuál es el mejor bandido se continuará jugando una cantidad de veces con bandidos que no son el óptimo. Lo que se puede resolver utilizando una estrategia Epsilon-Greedy con decaimiento. Esto es, cambiando la probabilidad con la que se juega con bandidos aleatorios a medida que aumenta el conocimiento del agente del entorno.

La estrategia Epsilon-Greedy con decaimiento

Uno de los problemas de la estrategia Epsilon-Greedy es que independientemente del número de episodios continúa explorando con todos los bandidos el mismo porcentaje de veces. Algo que no es necesario cuando se conoce cuál es el bandido óptimo. La solución de este problema es sencilla, simplemente reducir el valor de épsilon, el porcentaje de veces que se juega aleatoriamente, a medida que aumenta el número de episodios. De este modo, en los primeros episodios, cuando se desconoce la recompensa esperada, se juega aleatoriamente y, a medida que se tiene más información, se juega de manera óptima.

Decaimiento del parámetro épsilon

Se pueden usar diferentes estrategias para obtener un valor de épsilon que decaiga con el tiempo. Ya que solamente es necesario que este decaiga a medida que aumente el número de episodios. Por lo que una de las formas más sencillas sería usar un valor inversamente proporcional al número de episodios, resto es, 1/N donde N es el número de episodios.

Otra opción, la que se va a implementar a continuación, es comenzar con un valor de épsilon dado y reducir el valor de este multiplicándose en cada episodio por un factor que sea menor inferior a la unidad. Así, el valor en cada tirada sería epsilon * decay^N donde, al igual que antes, N es el número de episodios.

Publicidad


Implementación de Epsilon-Greedy con decaimiento en Python

Para implementar el método de Epsilon-Greedy se van a crear dos clases. Una clase Bandit en la que se implementa un bandido con una recompensa que se genera mediante una distribución binomial. Por otro lado, la clase Epsilon en la que se implementa el agente. Código que se muestra a continuación.

import numpy as np
import matplotlib.pyplot as plt

class Bandit:
    """
    Implementación de un Bandido Multibrazo (Multi-Armed Bandit) basado
    en una distribución binomial

    Parámetros
    ----------
    number: integer
        Número de recompensas que puede devolver el agente
    probability : float
        Probabilidad de que el objeto devuelva una recompensa
    
    Métodos
    -------
    pull :
        Realiza una tirada en el bandido
        
    """
    def __init__(self, probability, number=1):
        self.number = number
        self.probability = probability
        
        self.reward = self.number * self.probability
        
        
    def pull(self):        
        return np.random.binomial(self.number, self.probability)
    
    
class Epsilon:
    """
    Agente que soluciona el problema del el Bandido Multibrazo
    (Multi-Armed Bandit) mediante el uso de una estrategia Epsilon
    Greedy
    
    Parámetros
    ----------
    bandits : array of Bandit
        Vector con los bandidos con los que se debe jugar
    epsilon : float
        Porcentaje de veces en las que el agente jugada de forma
        aleatoria
    decay : float
        Velocidad con la que decae la probabilidad de seleccionar una
        jugada al azar
        
    Métodos
    -------
    run :
        Realiza una tirada en el bandido
    average_reward :
        Obtención de la recompensa promedio
    plot :
        Representación gráfica del histórico de jugadas
    reset :
        Reinicia el agente
    """
    
    def __init__(self, bandits, epsilon=0.05, decay=1):
        self.bandits = bandits
        self.epsilon = epsilon
        self.decay = decay
        
        self.reset()
        
    def run(self, episodes=1):
        for i in range(episodes):
            prob = np.random.random()
            
            # Selección entre la jugada aleatoria o avariciosa
            if prob < self._epsilon:
                bandit = np.random.choice(len(bandits))
            else:
                max_bandits = np.where(self._mean == np.max(self._mean))[0]
                bandit = np.random.choice(max_bandits)

            # Decaimiento del parámetro epsilon
            self._epsilon *= self.decay
            
            # 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
        
        return self.average_reward()
    
    
    def average_reward(self):
        return np.mean(self._rewards)
    
    
    def plot(self, log=False, reference=False, label=None):
        cumulative_average = np.cumsum(self._rewards) / (np.arange(len(self._rewards)) + 1)
        
        if label is None:
            plt.plot(range(len(self._rewards)), cumulative_average)
        else:
            plt.plot(range(len(self._rewards)), cumulative_average, label=label)
            
        if reference:
            for reward in [b.reward for b in self.bandits]:
                plt.plot([0, len(self._rewards)], [reward, reward],
                         label=f'reward={reward}')
                
        if log:
            plt.xscale('log')
    
    
    def reset(self):
        self._epsilon = self.epsilon
        self._rewards = []
        self._plays = [0] * len(self.bandits)
        self._mean = [0] * len(self.bandits)  

La clase Bandit

En la clase Bandit existen dos propiedades: number que indica la recompensa máxima que se puede obtener en una tirada, valor que por defecto es igual a la unidad, y probability la probabilidad de éxito. Además de esto se calcula la recompensa promedio esperada, lo que para una distribución binomial es el producto de los dos parámetros.

Solamente se ha implementado un método, pull(), a través del cual se obtiene el resultado de una tirada.

La clase es una simplificación de la que usamos en entradas anteriores, ya que no guarda las recompensas históricas ni el promedio de estas. Lo que se ha implementado en esta ocasión dentro de la clase Epsilon

Publicidad


La clase Epsilon

El código de la clase Epsilon es más compleja, ya que incluye la lógica del agente. Una clase que cuenta con tres parámetros: bandits un vector con el listado de bandidos, epsilon la probabilidad con la que jugará al azar el agente y decay el parámetro con el que decae el valor epsilon. Por otro lado, la clase cuenta con cuatro métodos run(), average_reward(), plot() y reset()

run()

El método run() jugará el número de episodios indicadas con los bandidos. En primer lugar, calculará un valor al azar y si este es menor que el valor de épsilon lo hará al azar, mientras que en el resto de los casos seleccionará el mejor agente. Al igual que se hizo para el caso de Epsilon-Greedy, en el caso de una recompensa promedio se seleccionará el bandido al azar. Posteriormente, se jugará con el bandido y se calculará el nuevo valor de épsilon, se agregará la recompensa al histórico y se actualizará la recompensa promedio para cada bandido. Devolviendo como resultado la recompensa promedio.

Algo que se puede ver en el código es que si el valor de decay es igual a la unidad, valor por defecto, entonces la clase implementa el método Epsilon-Greedy normal. Para implementar Epsilon-Greedy con decaimiento es necesario que decay sea un valor menor que 1 y positivo.

average_reward()

El método average_reward() simplemente calcula la recompensa promedio para el agente.

Publicidad


plot()

El método plot() permite representar la recompensa media acumulada para ver cómo evoluciona esta con el tiempo. Gráfica a la que se puede añadir la recompensa promedio que se esperaría para cada agente. Opcionalmente también se puede cambiar el eje de coordenadas x para que se emplee escala logarítmica, algo que es de gran utilidad cuando el número de episodios es elevado.

reset()

Finalmente, el método reset() permite reiniciar el agente. Algo que se puede utilizar si se desea volver a jugar con los mismos bandidos desde el principio.

Resultados

Ahora se puede comparar los resultados que se obtienen para 10.000 episodios con Epsilon-Greedy y Epsilon-Greedy con decaimiento. Para lo que solamente se tendría que usar el siguiente código.

np.random.seed(0)

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

epsilon = Epsilon(bandits)
decay = Epsilon(bandits, epsilon=1, decay=0.999)

epsilon.run(10000)
decay.run(10000)

Lo primero que se puede ver es que el método sin decaimiento tiene una recompensa de 0,093, mientras el método con decaimiento de 0,094. Una ligera mejora para el segundo, pero que todavía no es significativa.

Publicidad


El valor que se debería esperar para el método sin decaimiento es de 0,098. Esto es 95% por la recompensa del mejor bandido más 5% por la recompensa promedio de todos los bandidos. Esto es: 0,95 * 0,1 + 0,05 * (0,18/3) lo que da 0,098.

Por otro lado, a medida que aumenta el número de episodios el valor de Epsilon-Greedy con decaimiento debe acercarse al del mejor bandido. Ya que, el valor de épsilon tenderá a cero, por lo que solamente jugará con este.

Esto es algo que se puede comprobar aumentando el número de episodios. Por ejemplo, con un millón de episodios más los valores pasarán a ser de 0,0985 y 0.0998 para Epsilon-Greedy y Epsilon-Greedy con decaimiento respectivamente. Valores ya muy cercanos a los que se esperaría para ambos agentes.

La evolución de los 1,1 millón de episodios se puede ver en la siguiente gráfica. En donde se puede ver que ambas estrategias se acercan al valor óptimo a partir de los 10.000 episodios.

Publicidad


Evolución de los resultado de Epsilon-Greedy y Epsilon-Greedy con decaimiento después de 1,1 millones de episodios
Evolución de los resultado de Epsilon-Greedy y Epsilon-Greedy con decaimiento después de 1,1 millones de episodios

Conclusiones

La estrategia Epsilon-Greedy con decaimiento ofrece ciertas ventajas respecto a Epsilon-Greedy, especialmente cuando el número de episodios aumenta. Al seleccionar el bandido inicialmente al azar y, a medida que avanzan los episodios, cada vez de una forma más avariciosa permite obtener mayores recompensas. Ya que una vez que se conoce cual es el mejor bandido ya no es necesario explorar en busca del mejor.

Image by pasja1000 from Pixabay

¿Te ha parecido de utilidad el contenido?

¡Puntúalo entre una y cinco estrellas!

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

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?

Publicaciones relacionadas

  • feng-shui
    Test A/B para el Bandido Multibrazo (Multi-Armed Bandit)
  • lake
    Algoritmos de seguimiento (pursuit) para un problema…
  • prairie
    Muestreo de Thompson y BayesUCB para un problema…
  • autumn
    Softmax para un problema Bandido Multibrazo…
  • peak
    UCB1 para un problema Bandido Multibrazo…
  • landscape
    KL-UCB para un problema Bandido Multibrazo…

Publicado en: Ciencia de datos Etiquetado como: Aprendizaje por refuerzo, Machine learning

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.

Publicidad





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
  • Facebook
  • GitHub
  • Instagram
  • Pinterest
  • RSS
  • Twitter
  • Tumblr
  • YouTube

Publicidad

Entradas recientes

Mantener un sistema de alta disponibilidad con PostgreSQL y repmgr

diciembre 1, 2023 Por Daniel Rodríguez

Diferencias entre los errores 401 y 403 del estándar HTTP

noviembre 29, 2023 Por Daniel Rodríguez

Ver el código de cualquier función en Python

noviembre 27, 2023 Por Daniel Rodríguez

Publicidad

Es tendencia

  • El método Sainte-Laguë y su implementación en Python publicado el septiembre 22, 2023 | en Ciencia de datos
  • Operaciones de filtrado de DataFrame con Pandas en base a los valores de las columnas publicado el mayo 10, 2019 | en Python
  • NumPy NumPy: Crear matrices vacías en NumPy y adjuntar filas o columnas publicado el enero 11, 2021 | en Python
  • ¿Cómo cambiar el nombre de las columnas en Pandas? publicado el mayo 6, 2019 | en Python
  • Ordenación de diccionarios en Python mediante clave o valor publicado el enero 14, 2019 | en Python

Publicidad

Lo mejor valorado

4.9 (22)

Seleccionar filas y columnas en Pandas con iloc y loc

4.7 (12)

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

4.6 (15)

Archivos JSON con Python: lectura y escritura

4.5 (10)

Diferencias entre var y let en JavaScript

4.4 (13)

Ordenación de diccionarios en Python mediante clave o valor

Publicidad

Comentarios recientes

  • Anto en Rendimiento al iterar en JavaScript sobre un vector
  • Daniel Rodríguez en Creación de un certificado Let’s Encrypt en Windows con Win-Acme
  • Guillermo en Creación de un certificado Let’s Encrypt en Windows con Win-Acme
  • Daniel Rodríguez en ¿Cómo eliminar columnas y filas en un dataframe pandas?
  • Miguel en ¿Cómo eliminar columnas y filas en un dataframe pandas?

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-2023 Analytics Lane ·Términos y condiciones ·Política de Cookies ·Política de Privacidad ·Herramientas de privacidad ·Contacto