Aprendizaje por refuerzo (RL) — Capítulo 3: Multi-armed bandit — Parte 3: Implementación en Python

7 min readDec 6, 2023

Y llegamos a la ultima parte de este capítulo. En las partes anteriores vimos como funcionan diferentes estrategias para resolver el problema de Multi-armed bandit como Epsilon-greedy y Epsilon-decreasing, Upper Confidence Bound, Softmax y Multi-armed bandit con muestreo de Thompson, y en esta parte vamos a ver como implementar dichas estrategias en Python.

Epsilon-decreasing

Vamos a arrancar por la primera de las estrategias, Epsilon-decreasing, que la estudiamos en la primer parte de esta capítulo.

Lo primeros que debemos hacer es inicializar nuestros parámetros, que recordemos que son las estimaciones iniciales de Q (que los inicializaremos con un valor de 0.5 para todas las acciones), los valores de ϵ para cada época de entrenamiento, los valores de k (que contabilizan cuantas veces se seleccionó cada acción y que van a ser 0 para cada acción inicialmente) y finalmente la cantidad de épocas de entrenamiento

# Pasos de entrenamiento.
epocas = 10000

# Epsilon-decreasing.
epsilon_greedy = np.logspace(0,-5, epocas)

# Se crea una lista para contar cuantas veces se tomo cada decision.
k = np.zeros(len(probabilidades))

# Inicializamos el vector de probabilidades estimadas.
Q = 0.5*np.ones(len(probabilidades))

Podemos observar que tanto Q como k dependen de una variable llamada probabilidades. Estas probabilidades es lo que queremos descubrir o, mejor dicho, cual de estas probabilidades es mayor. Estos valores, en un problema del mundo real, son desconocidas para nosotros (nuestro agente realmente) pero aquí las vamos a definir para poder realizar la simulación

# Probabilidades de ganar de cada tragamonedas (desconocida a priori).
probabilidades = [0.25, 0.35, 0.55, 0.60]

Una vez definidos todos los parámetros podemos programar nuestro algoritmo de Epsilon-decreasing

R = []
for i in tqdm(range(epocas)):
    eps = epsilon_greedy[i]
    rnd = np.random.rand()

    # Si el valor aleatorio es menor al valor 
    # de epsilon elegimos una tragamoneda al azar.
    if rnd<eps:
        action = np.random.choice(range(len(Q)))
    # Si es mayor, elegimos la tragamoneda que tiene mayor probabilidad (segun nuestra estimación).
    else:
        action = np.argmax(Q)

    # Devuelve una recompenza de 1 si ganamos y de 0 si no.
    reward = 1*(np.random.rand()<=probabilidades[action])
    R.append(reward)

    # Actualizamos las probabilidades estimadas segun la ecuación vista.
    Q[action] = Q[action] + 1.0/(1.0+k[action]) * (reward-Q[action])
    k[action] += 1

Analicemos que sucede aquí. Dentro del primer paso del bucle definimos el valor de ϵ para la época actual (que seteamos con un decaimiento logarítmico para cada época). Luego generamos un valor aleatorio entre 0 y 1 y comprobamos si el mismo es menor a ϵ.

Si es menor a ϵ entonces tomamos una acción aleatoria y si no lo es elegimos la acción que maximiza nuestro vector de valores Q. Finalmente aplicamos la acción a nuestro entorno y obtenemos la recompensa.

Por ultimo realizamos la actualización de nuestro vector de valor Q según la ecuación

Este proceso se repite para cada época hasta finalizar el entrenamiento.

Upper Confidence Bound

El segundo algoritmo que vamos a implementar es el de Upper Confidence Bound. Igual que antes primero tenemos que inicializar los parámetros del modelo

# Pasos de entrenamiento.
epocas = 10000

# Se crea una lista para contar cuantas veces se tomo cada decision.
n_i = {i:1 for i in range(len(probabilidades))}

# Inizializamos un diccionario para guardar los historicos de recompanzas obtenidas.
mu_i = {i:[0.5] for i in range(len(probabilidades))}

# Iniziamos el vector de recompenzas estimadas.
Q = np.zeros(len(probabilidades))

Aquí los parámetros que inicializamos son nᵢ, que es el número de veces que se ha seleccionado la acción (equivalente a Nₐ), μᵢ para almacenar el histórico de recompensas obtenidas para cada acción, Q y la cantidad de épocas como en el algoritmo anterior. Al igual que antes tambien definimos el vector de retornos reales de cada acción.

Una vez definidos los parámetros inicializamos el proceso de entrenamiento

R = []
for ni in tqdm(range(epocas)):
    # Calculamos la cantidad de iteraciones.
    n = sum(n_i.values())
    
    # Calculamos la recompenza estimada de cada tragamoneda.
    Q = [np.mean(mu_i[i]) for i in range(len(probabilidades))]
    
    # Elegimos la mejor acción segun la ecuacion vista.
    action = np.array([Q[i] + np.sqrt(2*np.log(n)/n_i[i]) for i in range(len(probabilidades))]).argmax()
    
    # Devuelve una recompenza de 1 si ganamos y de 0 si no.
    reward = 1*(np.random.rand()<=probabilidades[action])
    R.append(reward)
    
    # Agregamos la recompenza al historico de esa acción.
    mu_i[action].append(reward)
    
    # Sumamos una interacción a esa tragamoneda.
    n_i[action] +=1

Aquí los pasos son los siguientes: primero calculamos el valor total de n (N = ∑ Nₐ), luego calculamos las recompensas estimadas de cada acción como el promedio de las recompensas obtenidas hasta el momento, y finalmente tomamos la acción según la ecuación

Por ultimo, al igual que antes, aplicamos la acción al entorno, obtenemos la recompensa, la guardamos en el histórico μᵢ de dicha acción y sumamos 1 a la cantidad de veces que seleccionamos esta acción. Finalmente repetimos el proceso para cada época hasta finalizar el entrenamiento.

Softmax Algorithm

Aca, al igual que con Epsilon-decreasing, definimos los mismos parámetros excepto que en vez de setear el valor de ϵ, seteamos el valor de τ (hiperparámetro que determina la cantidad de aleatorización al elegir una acción).

Luego, el proceso de entrenamiento es el siguiente

R = []
for i in tqdm(range(epocas)):
    # Elegimos una acción con la probabilidad dada por softmax.
    action = np.random.choice(len(Q),p=softmax(Q/t))

    # Devuelve una recompenza de 1 si ganamos y de 0 si no.
    reward = 1*(np.random.rand()<=probabilidades[action])
    R.append(reward)

    # Actualizamos las probabilidades estimadas segun la ecuación vista.
    Q[action] = Q[action] + 1.0/(1.0+k[action]) * (reward-Q[action])
    k[action] += 1

Primero elegimos la acción a partir de la probabilidad calculada como

Aplicamos la acción al entorno y obtenemos la recompensa para actualizar nuestro vector de valor a partir de la ecuación

Como siempre, repetimos este proceso para todas las épocas.

Multi-armed bandit con muestreo de Thompson

Por último, el algoritmo de Multi-armed bandit con muestreo de Thompson. Como es costumbre primero definimos los parámetros de nuestro agente:

# Creamos la lista de alpha y beta para cada acción.
alphas = [1 for _ in range(len(probabilidades))]
betas = [1 for _ in range(len(probabilidades))]

Aquí inicializamos los valores de α y β ambos en 1 para todas las acciones que corresponde a una distribución uniforme. Luego de definir las probabilidades y la cantidad de épocas pasamos al proceso de entrenamiento

R = []
for ni in tqdm(range(epocas)):
    # Tomamos un valor aleatorio de cada distribucion.
    rnd_values = [np.random.beta(alphas[i], betas[i]) for i in range(len(probabilidades))]
    
    # Elegimos la mejor acción.
    action = np.argmax(rnd_values)
    
    # Devuelve una recompenza de 1 si ganamos y de 0 si no.
    reward = 1*(np.random.rand()<=probabilidades[action])
    R.append(reward)
    
    # ACtualizamos los valores de alpha y beta a esa acción.
    alphas[action] += reward
    betas[action] += 1-reward

El proceso es el siguiente: primero estimamos el valor de cada acción tomando un valor aleatorio determinado por la distribución beta de cada acción. Luego elegimos la acción con mayor valor y la aplicamos al entorno para obtener la recompensa y actualizar nuestro agente a partir de

El proceso se repite para todas las épocas.

Y eso es todo lo que necesitamos para implementar estas estrategias en Python. Recuerde que tiene a su disposición las notebooks con el código que acabamos de analizar en el repositorio de Git:

GitHub - jcerretani/AprendizajePorRefuerzo

Contribute to jcerretani/AprendizajePorRefuerzo development by creating an account on GitHub.

github.com

En el próximo capítulo trabajemos con los algoritmos de Min-Max y Alpha-Beta Pruning, dos algoritmos que tuvieron y tienen mucho impacto en la resolución de problemas, especialmente en juegos de mesa y que fueron la base para vencer al campeón mundial del ajedrez Garry Kasparov.

No se lo pierdan!