Multi-armed bandit para la elección del landing page
Más sobre ciencia de datos: cienciadedatos.net
En este artículo exploraremos cómo el uso de técnicas de aprendizaje reforzado, concretamente el Multi-armed bandit nos permite reducir el tiempo necesario para valorar si una nueva versión de nuestra página web es más eficaz a la hora de aumentar nuestro número de clientes.
Contexto de negocio¶
Uno de los aspectos clave de las actividades de marketing es convertir las visitas a nuestra web en una llamada a la acción (del inglés CTA- Call To Action) de los clientes potenciales que llegan a nuestra página principal.
Por ello es muy importante que el contenido de esa página principal sea atractivo y favorezca ese CTA, ya sea registrarse como usuario, seguir navegando en la web o solicitar descargar nuestro catálogo.
Pero, ¿qué sucede cuando queremos desplegar una nueva versión y no estamos seguros de su efectividad? En estos casos, solemos redirigir parte del tráfico a la versión antigua de la web y otra parte a la nueva, hasta tener una muestra representativa que nos permita valorar si efectivamente el esfuerzo de desarrollo de la nueva versión se refleja en un aumento de esa conversión de visitas en clientes potenciales, lo que denominamos A/B testing.
Al ser una valoración a posteriori, tras cierto tiempo con ambas versiones en línea, se incurre en un coste de oportunidad (el de mantener también activa la versión menos eficaz) que dada la competencia creciente a la que nos enfrentamos en algunos negocios resulta poco deseable o incluso inadmisible.
Uso del aprendizaje reforzado¶
En este contexto, en el que queremos comparar dos o más versiones de nuestra página de bienvenida, el aprendizaje reforzado nos brinda la posibilidad de acelerar nuestra toma de decisiones y disminuir el coste de oportunidad, al ir favoreciendo paulatinamente aquella versión a la que nuestros clientes reaccionan mejor para poco a poco ir disminuyendo el tráfico dirigido a la alternativa o alternativas menos deseables.
Durante el entrenamiento, tendremos que buscar el balance entre decantarnos por la opción en ese momento más efectiva (explotación) frente a permitir también dirigir el tráfico hacia las versiones aparentemente menos eficientes (exploración) para continuar con el aprendizaje.
Multi-armed Bandit¶
En el aprendizaje reforzado, el agente genera sus propios datos de entrenamiento interactuando con el entorno. El agente debe aprender las consecuencias de sus acciones mediante ensayo y error, en lugar de con un conocimiento a priori de la acción correcta.
En el caso concreto del Multi-armed bandit, nos encontramos con k opciones diferentes o acciones. Tras efectuar una acción, obtenemos una recompensa numérica escogida de una distribución de probabilidad, que tendrá que ser estacionaria y dependerá de dicha acción seleccionada. Nuestro objetivo será el de maximizar la recompensa total para un periodo de tiempo, por ejemplo, 1000 acciones o pasos temporales.
En nuestro problema, cada acción tiene una recompensa media esperada al ser seleccionada, denominada valor de la acción. Para cualquier acción, tendremos:
$$q_*(a) \doteq \mathbf{E}[R_t|A_t=a]$$Si supiésemos el verdadero valor de cada acción, entonces resolver el problema del Multi-armed bandit sería trivial, ya que siempre seleccionaríamos aquella acción con un mayor valor esperado. Asumimos que no lo conocemos con certeza, aunque sí podemos tener estimaciones, las cuales denotamos como $Q_t(a)$, la recompensa esperada en el paso de tiempo $t$ al tomar la acción $a$ y trataremos que sea lo más cercana posible a $q_*(a)$.
Para un mayor detalle en cuanto a los conceptos detrás del Multi-armed bandit y el pseudocódigo necesario para su implementación, se recomienda la lectura de Reinforcement Learning: An Introduction, páginas 25-36.
En cada instante de tiempo, el agente escogerá entre explorar, con probabilidad $p$, seleccionando aleatoriamente de entre las distintas acciones o bien explotar, con probabilidad $1-p$, escogiendo hasta ese momento la acción con un valor esperado estimado mayor. En aprendizaje reforzado, denominamos a este tipo de agentes como Epsilon greedy.
Caso de uso y formalización como un problema de aprendizaje reforzado¶
Tomemos para nuestro caso de uso las siguientes consideraciones:
Queremos evaluar 3 versiones de nuestra web de entrada diferentes: la versión inicial (0) y las alternativas (1) y (2).
Asumiremos una llegada de 100.000 visitantes a nuestra web a los que habrá que redireccionar a cualquiera de las distintas versiones.
Consideraremos un éxito si el visitante realiza esa llamada a la acción (CTA).
Formalización como aprendizaje reforzado¶
- El set de acciones tiene cardinalidad 3: {asignar versión actual, asignar versión nueva 1, asignar versión nueva 2}.
- La recompensa será un 1 si se realiza la llamada a la acción y un 0 si no.
Experimentos¶
- Experimento 1: evaluar un agente con una probabilidad de exploración del 15%.
- Experimento 2: evaluar agentes con diferentes probabilidades de exploración entre 0% y 50%.
Consideraciones adicionales¶
- Nuestra versión inicial consigue el CTA en un 50% de los casos y lo modelaremos como una distribución uniforme entre 0 y 1.
- La versión nueva 1 consigue el CTA en un 75% de los casos y la versión nueva 2 en un 25%.
Por tanto, la recompensa acumulada esperada de nuestro experimento sería también la de mantener la versión actual, 50.000 (100.000 visitantes x 50% de probabilidad del CTA) y la máxima 75.000. Evaluaremos qué estrategia de aprendizaje provee una mayor recompensa acumulada.
Información de sesión¶
from sinfo import sinfo
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from tqdm import tqdm
sinfo()
plt.hlines(0.75, 0, 100000, colors='green', linestyles='solid', label='max reward')
plt.hlines(0.25, 0, 100000, colors='red', linestyles='solid', label='min reward')
plt.hlines(0.5, 0, 100000, colors='blue', linestyles='solid', label='avg reward');
Creación del entorno¶
Implementaremos un entorno muy sencillo en el que cada acción nos reporta un éxito con una probabilidad $p_a$. Validaremos asimismo que la recompensa esperada de la primera acción es en torno al 50% de los pasos, del 75% para la acción 1 (correspondiente a la nueva versión 1) y 25% para la acción 2.
class environment:
def __init__(self, probabilities):
"""
Arguments:
probabilities: `list` or `np.array` with the probabilities of success of each action.
"""
self.probabilities = probabilities
def step(self, action):
"""
Environment step returning the reward of each action
Arguments:
action: `int`
"""
return 1.0*(np.random.uniform(0,1) <= self.probabilities[action])
env = environment([0.5, 0.75, 0.25])
n_steps = 10000
print("Recompensa promedio:\nacción 0:{}\nacción 1:{}\nacción 2:{}\n".format(
np.mean([env.step(0) for i in range(n_steps)]),
np.mean([env.step(1) for i in range(n_steps)]),
np.mean([env.step(2) for i in range(n_steps)])
))
Implementación del agente¶
def argmax(q_values):
"""
Takes in a list of q_values and returns the index
of the item with the highest value. Breaks ties randomly.
returns: int - the index of the highest value in q_values
"""
top = float("-inf")
ties = []
for i in range(len(q_values)):
if q_values[i] > top:
top, ties = q_values[i], [i]
elif q_values[i] == top:
ties.append(i)
ind = np.random.choice(ties)
return ind
class EpsilonGreedyAgent():
def __init__(self, action_size = 3, epsilon = 0.15):
"""
This class implements an epsilon-greedy agent that takes with probability epsilon a random action
and with probability 1-p the action with the highest q-value
Arguments:
epsilon: `float` with the exploration probability
action_size: `int` cardinality of the action space
Attributes:
last_action: `int` with the last action taken by the agent
arm_count: `numpy.array` with the number of times each action has been taken
q_values: `numpy.array` with the value estimates of taking each action
"""
# epsilon: probabilidad de exploración del agente
self.epsilon = epsilon
# last_action: accion tomada en el paso previo
self.last_action = None
# arm_count: número de veces que cada acción se ha tomado
self.arm_count = np.zeros(action_size)
# q_values: array con el valor estimado q por el agente para cada opción
self.q_values = np.zeros(action_size)
def agent_init(self):
"""
Initialization of the agent to take the first action randomly
"""
current_action = np.random.randint(len(self.q_values))
self.last_action = current_action
return current_action
def agent_step(self, reward):
"""
Takes one step for the agent. It takes in a reward and observation and
returns the action the agent chooses at that time step.
Arguments:
reward: `float`, the reward the agent received from the environment after taking the last action.
Returns:
current_action : `int`, the action chosen by the agent at the current time step.
"""
self.arm_count[self.last_action] += 1
self.q_values[self.last_action] += (reward - self.q_values[self.last_action]) / self.arm_count[self.last_action]
if np.random.random() < self.epsilon:
current_action = np.random.randint(len(self.q_values))
else:
current_action = argmax(self.q_values)
self.last_action = current_action
return current_action
Agente con tasa de exploración del 15%¶
En este primer experimento vamos a evaluar el comportamiento del agente en 200 simulaciones de llegada de 100000 clientes. La probabilidad de exploración será del 15% y la recompensa máxima teórica que podemos lograr estará en 0.75, correspondiendo a una tasa de conversión de 3 de cada 4 clientes al realizar estos el CTA.
num_runs = 200 # Número de veces que repetimos el experimento
num_steps = 100000 # Número de visitas (pasos) por experimento
probabilities = [0.5, 0.75, 0.25]
epsilon = 0.15
all_averages = []
actions = []
for i in tqdm(range(num_runs)):
env = environment(probabilities) # Inicializamos el entorno
agent = EpsilonGreedyAgent(action_size = 3, epsilon = epsilon) # Inicializamos el agente
action = agent.agent_init()
actions.append(action)
scores = [0]
averages = []
for i in range(num_steps):
reward = env.step(action)
action = agent.agent_step(reward)
actions.append(action)
scores.append(scores[-1] + reward)
averages.append(scores[-1] / (i + 1))
all_averages.append(averages)
Recompensa acumulada promedio¶
plt.figure(figsize=(11, 4), dpi= 80, facecolor='w', edgecolor='k')
plt.plot([0.75 for _ in range(num_steps)], linestyle="--")
plt.plot(np.mean(all_averages, axis=0))
plt.legend(["Best Possible", "Epsilon-Greedy 15%"])
plt.title("Average Reward of Epsilon-Greedy Agent")
plt.xlabel("Steps")
plt.ylabel("Average reward")
plt.show()
greedy_scores = np.mean(all_averages, axis=0)
np.save("greedy_scores", greedy_scores)
Acciones seleccionadas¶
pd.Series(actions).hist();
print("Recompensa promedio:{:.3f}\n\n*Estimaciones*\nacción 1:{:.3f}\nacción 2:{:.3f}\nacción 3:{:.3f}\n".format(
np.mean(all_averages, axis=0)[-1],
agent.q_values[0], agent.q_values[1], agent.q_values[2]
))
Observamos que rápidamente nos decantamos por la opción exitosa, a pesar de no llegar al 75% teórico de conversión de visitas, estamos en torno al 71%, lo cual supondría una mejora del 21% respecto a la conversión que tenía nuestra versión inicial de la web y solo un coste oportunidad, de conversiones que no logramos capturar, del 4%.
También podemos comprobar cómo la acción 1, correspondiente con la primera de las nuevas versiones de la web es la seleccionada con una frecuencia varios órdenes de magnitud mayor que las otras dos. Por último, comprobamos que los valores de cada acción son bastante cercanos a los valores verdaderos de $(0.5, 0.75, 0.25)$.
Comparativa de valores de exploración y explotación¶
Ahora veremos en un segundo experiment si es posible hacer que disminuya el coste oportunidad ponderando de manera diferente la exploración y la explotación. Tomaremos 5 opciones diferentes, entre un 0%, que representaría tomar siempre la acción con el mayor valor estimado y un 50%, que representaría una toma de decisiones dicotómica entre una acción aleatoria y la mejor acción hasta ese momento.
Encontrar un buen equilibrio entre explotar la mejor acción y explorar nuevas opciones es vital, ya que un valor muy pequeño de la exploración nos conduciría a seleccionar sistemáticamente una acción subóptima mientras que unos valores muy altos conllevarían un comportamiento errático del agente que no aportaría ningún valor.
epsilons = [0.0, 0.01, 0.1, 0.4, 0.5]
num_runs = 200
num_steps = 50000
per_epsilon = {}
per_epsilon_action = {}
for epsilon in epsilons:
all_averages = []
all_actions = []
for i in tqdm(range(num_runs)):
env = environment(probabilities) # Inicializamos el entorno
agent = EpsilonGreedyAgent(action_size = 3, epsilon = epsilon) # Inicializamos el agente
action = agent.agent_init()
scores = [0]
averages = []
actions = [action]
for i in range(num_steps):
reward = env.step(action)
action = agent.agent_step(reward)
scores.append(scores[-1] + reward)
averages.append(scores[-1] / (i + 1))
actions.append(action)
all_averages.append(averages)
all_actions.append(actions)
per_epsilon[epsilon] = all_averages
per_epsilon_action[epsilon] = all_actions
Recompensa acumulada promedio¶
plt.figure(figsize=(11, 4), dpi= 80, facecolor='w', edgecolor='k')
plt.plot([0.75 for _ in range(num_steps)], linestyle="--")
plt.plot(np.mean(per_epsilon[0.0], axis=0))
plt.plot(np.mean(per_epsilon[0.01], axis=0))
plt.plot(np.mean(per_epsilon[0.1], axis=0))
plt.plot(np.mean(per_epsilon[0.4], axis=0))
plt.plot(np.mean(per_epsilon[0.5], axis=0))
plt.legend(["Best Possible", "Greedy", "1%", "10%", "40%", "50%"])
plt.title("Average Reward of Epsilon-Greedy Agent")
plt.xlabel("Steps")
plt.ylabel("Average reward")
plt.show()
Acciones seleccionadas¶
pd.Series(np.array(per_epsilon_action[0.01]).reshape(-1)).hist();
En este experimento, podemos comprobar cómo la selección del parametro $\epsilon$, la probabilidad de tomar una acción aleatoria para favorecer la exploración, afecta al aprendizaje del agente.
Un agente "ávido" (greedy en inglés) satura rápidamente al 0.6 y no consigue salir de ese valor, mientras que valores elevados de aleatoriedad, correspondientes a probabilidades de un 40 a 50%, consiguen rendimientos marginalmente mejores pero inferiores a 0.65.
El valor óptimo parece corresponder a una tasa de exploración $\epsilon$ de entre el 1% (logra el mayor valor promedio) y el 10% (asciende mucho más rápido pero satura en torno al 0.72).
Contemplando las acciones seleccionadas para el agente que obtiene un valor promedio, vemos que explora tanto la opción 0 como la 2 pero rápidamente se decanta por la 1.
Integración del conocimiento a priori¶
Hasta ahora hemos considerado que partíamos de cero, sin ningún conocimiento de la tasa de conversión esperada de cada versión.
En el caso que nos ocupa esto no es del todo cierto, ya que tendríamos métricas de la versión inicial y podríamos usar ese conocimiento a priori para inicializar los valores de cada acción $Q_0(a)$.
Concluiremos con este experimento en el que usaremos el valor del 50%, correspondiente a la tasa de conversión de la página en ese momento operativa para inicializar el valor de cada una de nuestras acciones.
num_runs = 200 # Número de veces que repetimos el experimento
num_steps = 50000 # Número de visitas (pasos) por experimento
probabilities = [0.5, 0.75, 0.25]
epsilons = [0.0, 0.01, 0.1, 0.4, 0.5]
per_epsilon_priorkw = {}
for epsilon in epsilons:
all_averages = []
for i in tqdm(range(num_runs)):
env = environment(probabilities) # Inicializamos el entorno
agent = EpsilonGreedyAgent(action_size = 3, epsilon = epsilon) # Inicializamos el agente
agent.q_values = 0.5 * np.ones(3)
action = agent.agent_init()
scores = [0]
averages = []
for i in range(num_steps):
reward = env.step(action)
action = agent.agent_step(reward)
scores.append(scores[-1] + reward)
averages.append(scores[-1] / (i + 1))
all_averages.append(averages)
per_epsilon_priorkw[epsilon] = all_averages
plt.figure(figsize=(11, 4), dpi= 80, facecolor='w', edgecolor='k')
plt.plot([0.75 for _ in range(num_steps)], linestyle="--")
plt.plot(np.mean(per_epsilon_priorkw[0.0], axis=0))
plt.plot(np.mean(per_epsilon_priorkw[0.01], axis=0))
plt.plot(np.mean(per_epsilon_priorkw[0.1], axis=0))
plt.plot(np.mean(per_epsilon_priorkw[0.4], axis=0))
plt.plot(np.mean(per_epsilon_priorkw[0.5], axis=0))
plt.legend(["Best Possible", "Greedy", "1%", "10%", "40%", "50%"])
plt.title("Average Reward of Epsilon-Greedy Agent")
plt.xlabel("Steps")
plt.ylabel("Average reward")
plt.show()
En este caso vemos el potencial del uso del conocimiento a priori, no solo mejorando el valor promedio en alguna de las estrategias sino que además, de manera generalizada, haciendo que el aprendizaje sea más rápido. Podemos comprobarlo superponiendo la trayectoria de la recompensa acumulada promedio con y sin conocimiento a priori, verificando que, si bien convergen al mismo valor, el caso con conocimiento a priori lo hace más rápidamente.
plt.figure(figsize=(11, 4), dpi= 80, facecolor='w', edgecolor='k')
plt.plot([0.75 for _ in range(num_steps)], linestyle="--")
plt.plot(np.mean(per_epsilon_priorkw[0.01], axis=0))
plt.plot(np.mean(per_epsilon[0.01], axis=0))
plt.legend(["Best Possible", "1% w/prior knowledge", "1%"])
plt.title("Average Reward of Epsilon-Greedy Agent")
plt.xlabel("Steps")
plt.ylabel("Average reward")
plt.show()
Conclusiones y ámbito de aplicación¶
En este artículo hemos explorado cómo el aprendizaje reforzado nos puede servir a la hora de evaluar distintas opciones recogiendo feedback en línea de los usuarios.
Con el caso del Multi-armed bandit , hemos visto el impacto de balancear correctamente la exploración y la explotación de las acciones con un mayor valor estimado y el uso del conocimiento a priori para obtener unas estimaciones mejores y más rápidas de esos $q_*(a)$ de cada acción.
¿Cómo citar este documento?
Multi-armed bandit para la elección del landing page by Francisco Espiga, available under a CC BY-NC-SA 4.0 at https://www.cienciadedatos.net/documentos/py28-k-armed-bandit-evaluar-versiones-web-python.html 
¿Te ha gustado el artículo? Tu ayuda es importante
Mantener un sitio web tiene unos costes elevados, tu contribución me ayudará a seguir generando contenido divulgativo gratuito. ¡Muchísimas gracias! 😊
This work by Francisco Espiga is licensed under a Creative Commons Attribution 4.0 International License.