Saltar al contenido

Explotación o exploración: el gran dilema

    maquinas tragaperras

    Dentro del campo del aprendizaje por refuerzo existe una gran problema a la hora de realizar el entrenamiento, y ese es el problema del la exploración o explotación.

    Nunca se sabe realmente si al llegar a un punto determinado es mejor seguir explorando o quedarse con el máximo resultado de recompensa que tenemos en ese momento. En problemas pequeños puede ser muy fácil ver esto, pero en problemas donde toda la complejidad no cabe en la memoria es un gran problema, ya que por cada paso que tome el algoritmo este tendrá que volver a calcularlo todo.

    El caso más famoso para ver esto es el dilema del bandido multibrazo (o en inglés Multi-armed bandit), que ya expuso Herbert Robbins en el año 1952 Herbert Robbins, y que ya se usa en finanzas para calcular que opciones sobre una acción van a tener mejor resultado.

    He encontrado muy poca información en castellano sobre esto así que aquí va mi pequeña aportación al tema.

    Introducción

    La idea principal de este problema es que un día decides gastar tu fortuna de 1.000€ que tienes ahorrados desde hace tiempo. Como no tienes hobbies se te ocurre y te gustan las mátemáticas se te ocurre ir a una sala de juegos o casino donde existen una máquinas tragaperras o tragamonedas, que en inglés se llaman one-arm bandid (de ahí el nombre del problema) e intentar ganar el máximo de dinero posible.

    Cuando entras ves que hay cinco máquinas cada una diferente a las demás, y por tanto das por echo que cada uno tendrá premios distintos y distintas probabilidades de ganar. También en este caso hay que tener en cuenta que este casino es de lo más legal del mundo y no está para ganar dinero.

    tragaperras

    La pregunta es ¿Cómo podemos averiguar qué máquina es más rentable de todas ellas? Podemos escoger una al azar, pero nunca sabremos si esa es la mejor o la peor máquina y siempre nos quedaríamos con la duda. También podemos jugar en las máquinas aleatoriamente, pero siempre tendríamos la sensación de estar desperdiciando nuestro dinero en máquinas equivocadas.

    ¿Cómo podríamos averiguar cual es la mejor máquina? Y, antes de seguir, ¿Se os ocurre alguna forma de conseguirlo?

    Primer acercamiento

    Imaginemos que empiezas a gastar el mismo dinero en todas las máquinas y vas apuntado si te dan premio o no. Después de varias rondas por todas las máquinas tendrás alguna máquina que te ha dado más premios que otras. Así que a partir de ese momento podrías decidir apostar siempre a esa máquina. Pero ¿qué pasaría si esa máquina solo dio premios al principio y no los vuelve a dar más? Quizá la máquina que daría más premios a la larga no da un resultado significativo en ese periodo?

    Con todo esto surge otra pregunta ¿cuánto hay que probar hasta que los resultados nos devuelvan las verdaderas probabilidades de premio de una máquina?

    Con todo esto ya tenemos el verdadero problema de la exploración o explotación, tenemos que saber el equilibrio justo para aplicar un caso u otro. Así que vamos a ver las posibles soluciones que tenemos a esto.

    Estrategias

    Epsilon-avaricioso

    Esta estrategia es la más simple de todas donde balanceamos la exploración entre y la explotación aleatoriamente. Por ello, epsion \epsilon se refiere a la probabilidad de escoger explorar, con lo que según pongamos el valor decidirá entre explorar o explotar. Con lo que podemos decir que:

    (1)   \begin{equation*} acción(t)\left\{\begin{matrix} accion\;con\;mayor\;recompensa &con\;probalidad\;1-\epsilon \\  accion\;aleatoria &con\;probalidad\;\epsilon \end{matrix}\right. \end{equation*}

    Esto visto en python sería así:

    epsilon = 0.1
    aleatorio = np.random.random()
    if aleatorio > epsilon:
      print("Echo en la máquina con mayor recompensa")
    else:
      print("Escojo una máquina aleatoria")

    Epsilon-primero

    Esta estrategia también es muy sencilla y va por fases. Primero tendremos una fase completa de exploración durante un numero de veces N, después de eso siempre iremos a la opción con más recompensa.

    En python sería así:

    N=20
    # Fase de exploración
    for i in range(N):
      print("Escojo una máquina aleatoria")
    # Una vez que se ha hecho toda la labor de investigación
    # Ya siempre escoge la mejor
    print("Escojo la máquina con mayor recompesa")

    Epsilon-decreciente

    Es similar a Epsilon-avaricioso pero, en este caso, el valor de epsilon va decreciendo con el paso del tiempo. Con lo que si la estrategia va cambiando desde el valor inicial con un porcentaje de exploración determinado hasta un momento donde el algoritmo solo hará explotación de la mayor recompensa. Con esto aseguramos que la exploración sea en las primeras etapas del experimiento y según se va experimentando, el algoritmo se volverá más eficaz.

    Un ejemplo muy tonto python sería así:

    pruebas = 100
    for prueba in range(pruebas):
      aleatorio = np.random.random()
      epsilon = 1/((prueba+1)/10)
      if aleatorio > epsilon:
        print("Echo en la máquina con mayor recompensa")
      else:
        print("Escojo una máquina aleatoria")

    donde utilizamos la fórmula \frac{1}{(n+1)/10} para hacer un descenso muy gradual de la fórmula.

    Nota: Para aquellos que nunca entendieron los Límites en matemáticas este es un buen ejemplo de que al saber que \lim_{x\rightarrow +\infty}\frac{1}{x}=0 solo necesitamos hacer que vaya hacía 0 de la forma gradual que nosotros queramos.

    Valores iniciales optimistas

    Esta forma de buscar los mejores valores también es muy simple. Simplemente tenemos que poner unos valores iniciales a las máquinas muy superiores

    pruebas = 100
    maquinas = [100000,100000, 100000, 100000, 100000]
    for prueba in range(pruebas):
      # Escoger la máquina con la mayor recompansa
      mayor = np.argmax(maquinas)
      print("Echo en la máquina con mayor recompensa")
      # guardaríamos la recompensa que da la máquina con una media
      # y una desviación estandar para saber lo que puede variar

    Estrategias más avanzadas

    Existen otras muchas estrategias que son bástante más complejas y que requieren una entrada a solo para cada una de ellas debido a su complejidad, pero paso a explicar alguna de ellas:

    • Estrategia Epsilon-avaricioso adaptativa basada en diferencias de valor: Esta estrategia, también llamada VDBE (del inglés Value-Difference Based Exploration) es similar a la anterior, pero aquí en vez de bajar el epsilon de forma manual lo hace en base a un aprendizaje similar a la técnica del Q-Learning. Podeis leer más en su paper original.
    • Estrategia del bandido bayesiano: Esta estratégia como su nombre indica esta basada en el teorema de Bayes y en el distribución \beta. Esta no es que sea más complicada que el resto, pero creo que explicarla bien también llevaría un ratillo y prefiero dedicarle una entrada aparte.
    • Algoritmos de bandido con límite de confianza superior: Se busca conseguir un límite superior en la recompensa promedio de cada bandido, usando los datos que hemos recopilado hasta ahora. En cada paso, seleccionamos al bandido con el índice de confianza superior más alto, obtenemos la recompensa y posteriormente actualizamos su índice. Más información la podéis encontrar en el paper original.

    Conclusiones

    Esto ha sido una breve introducción al problema y a las soluciones más sencillas con un poco de pseudo-código, para que se pudieran entender. Aun hay muchas más soluciones que se pueden analizar, así que si miráis por internet podréis encontrar cual es la mejor fórmula para resolver este problema con el que seguro que os encontraréis incluso en vuestra primera inmersión en el aprendizaje por refuerzo.

    También podréis crear aquí vuestras propias soluciones a este problema (como he hecho yo en el epsilon-decreciente para que entendierais el ejemplo) y seguro que si os poneis a pensar y os gustan un poco las matemáticas podéis sacar vuestros propios algoritmos para resolver este problema.

    Como siempre, si tenéis cualquier duda o mejora del artículo no dudéis en poneros en contacto conmigo y os contestaré lo antes posible.

    Deja una respuesta

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