El dilema de exploración-explotación es un dilema que existe en muchas facetas de nuestra vida.Tomemos un ejemplo comunmente usado respecto a las posibles parejas que podríamos tener en nuestra vida y cuando sería el momento apropiado para “sentar cabeza”. Si tienes una pareja por mucho tiempo ya sabes el tipo de interacción que tienes, o la cantidad de momentos agradables vs problemas, que tienes con esta. Sin embargo, si cambias constantemente de pareja realmente no conoces del todo esta nueva persona, no sabes bien el tipo de interacción y lo bien o mal que te puedas llevar con estas parejas desconocidas. Sin embargo, el dilema consiste en como saber que la pareja con la que estas es la mejor opción y como saber cuando es tiempo de dejar de buscar otras parejas y elegir alguna. En esto consiste el dilema. Trasladandolo al campo de inteligencia artifical, si has aprendido toda la información acerca del ambiente, si sabemos absolutamente todas las parejas disponibles y el valor de cada una, la decisión es sencilla,solo tomar la de mayor valor. El problema existe cuando se tiene información incompleta, y necesitamos recolectar suficiente información para poder maximizar la recompensa y minimizar el riesgo. Una forma de cuantificar y hacer experimentación en el campo se refiere a los “bandidos”, que basicamente son máquinas al ser usadas tienen una cierta probabilidad para dar una cierta recompensa, el paradigma consiste en que el tiempo es limitado y solo puedes usar 1 en cada momento. La pregunta es: ¿Cual es la mejor estrategia para maximizar las recompensas?
Si tenemos a un agente que debe seleccionar que maquina usar. Lo primero que el agente debe de decidir es cual escoger.Aunque podriamos solo elegir aleatoriamente, queremos tener alguna creencia que justifique o describa cada decisión.Esto en la literatura se ejemplifica con el uso de una politica determinada por . También se necesita una función de valor por cada acción, al valor se le conoce como valor . El valor por tomar la acción en un tiempo determinado como que no dará el valor de la recompensa en este tiempo dada la acción elegida . La fórmula es la siguiente:
El objetivo sería el poder maximizar la recompensa la probabilidad optima de recompensa de la acción optima es:
Pero retomando lo aprendido acerca del dilema de exploración-exploración, si siempre tomamos la opción de mayor valor no sabemos bien cual es el valor del resto de las opciones o ¿de que nos estamos perdiendo? La solución más común a este problema es agregar un poco de aletoriedad al modelo. Determinar una probabilidad en la que se toma una acción diferente a la que tiene el valor máximo. Normalmente a esta estrategia se le llama “epsilon greedy”, que indica que 1 - para seleccionamos la opción con mayor valor o “greedy”, en caso contrario con una probabilidad pequeña elegimos una acción aleatoriamente (incluyendo la opción con mayor valor)
Otro concepto importante es REGRET , o “arrepentimiento”, básicamente es que tanto nos arrepentimos de seleccionar la acción elegida y no la opción optima en ese momento. Matematicamente la identificamos como:
Funciones para graficar y paqueterias.
Haz Clic para ver el Código
```{python}# @title Funciones para graficar y paquetesimport timeimport numpy as npimport matplotlib.pyplot as pltfrom scipy.signal import convolve as convfrom scipy.stats import betanp.set_printoptions(precision=3)def plot_choices(q, epsilon, choice_fn,c, n_steps=5000, rng_seed=1,init_a=1,init_b=1): np.random.seed(rng_seed) counts = np.zeros_like(q) asbeta = [init_a]*len(q) bsbeta = [init_b]*len(q)for t inrange(n_steps): action = choice_fn(q, epsilon,t,counts,asbeta,bsbeta,c) counts[action] +=1if np.random.random() < q[action]: reward=1else: reward=0# Observe the reward for the chosen action asbeta[action] += reward bsbeta[action] += (1- reward) fig, ax = plt.subplots() ax.bar(range(len(q)), counts/n_steps) ax.set(ylabel='% escogido', xlabel='acción', ylim=(0,1), xticks=range(len(q)))def plot_multi_armed_bandit_results(results): fig, (ax1, ax2, ax3) = plt.subplots(ncols=3, figsize=(20, 4)) ax1.plot(results['rewards']) ax1.set(title=f"Total Reward: {np.sum(results['rewards']):.2f}", xlabel='step', ylabel='reward') ax2.plot(results['qs']) ax2.set(xlabel='step', ylabel='value') ax2.legend(range(len(results['mu']))) ax3.plot(results['mu'], label='latent') ax3.plot(results['qs'][-1], label='learned') ax3.set(xlabel='action', ylabel='value') ax3.legend()def plot_parameter_performance(labels, fixed, trial_rewards, trial_optimal): fig, (ax1, ax2) = plt.subplots(ncols=2, figsize=(16, 6)) ax1.plot(np.mean(trial_rewards, axis=1).T) ax1.set(title=f'Average Reward ({fixed})', xlabel='step', ylabel='reward') ax1.legend(labels) ax2.plot(np.mean(trial_optimal, axis=1).T) ax2.set(title=f'Performance ({fixed})', xlabel='step', ylabel='% optimal') ax2.legend(labels)def plot_state_action_values(env, value, ax=None):if ax isNone: fig, ax = plt.subplots()for a inrange(env.n_actions): ax.plot(range(env.n_states), value[:, a], marker='o', linestyle='--') ax.set(xlabel='States', ylabel='Values') ax.legend(['R','U','L','D'], loc='lower right')def plot_quiver_max_action(env, value, ax=None):if ax isNone: fig, ax = plt.subplots() X = np.tile(np.arange(env.dim_x), [env.dim_y,1]) +0.5 Y = np.tile(np.arange(env.dim_y)[::-1][:,np.newaxis], [1,env.dim_x]) +0.5 which_max = np.reshape(value.argmax(axis=1), (env.dim_y,env.dim_x)) which_max = which_max[::-1,:] U = np.zeros(X.shape) V = np.zeros(X.shape) U[which_max ==0] =1 V[which_max ==1] =1 U[which_max ==2] =-1 V[which_max ==3] =-1 ax.quiver(X, Y, U, V) ax.set( title='Maximum value/probability actions', xlim=[-0.5, env.dim_x+0.5], ylim=[-0.5, env.dim_y+0.5], ) ax.set_xticks(np.linspace(0.5, env.dim_x-0.5, num=env.dim_x)) ax.set_xticklabels(["%d"% x for x in np.arange(env.dim_x)]) ax.set_xticks(np.arange(env.dim_x+1), minor=True) ax.set_yticks(np.linspace(0.5, env.dim_y-0.5, num=env.dim_y)) ax.set_yticklabels(["%d"% y for y in np.arange(0, env.dim_y*env.dim_x, env.dim_x)]) ax.set_yticks(np.arange(env.dim_y+1), minor=True) ax.grid(which='minor',linestyle='-')def plot_heatmap_max_val(env, value, ax=None):if ax isNone: fig, ax = plt.subplots()if value.ndim ==1: value_max = np.reshape(value, (env.dim_y,env.dim_x))else: value_max = np.reshape(value.max(axis=1), (env.dim_y,env.dim_x)) value_max = value_max[::-1,:] im = ax.imshow(value_max, aspect='auto', interpolation='none', cmap='afmhot') ax.set(title='Maximum value per state') ax.set_xticks(np.linspace(0, env.dim_x-1, num=env.dim_x)) ax.set_xticklabels(["%d"% x for x in np.arange(env.dim_x)]) ax.set_yticks(np.linspace(0, env.dim_y-1, num=env.dim_y))if env.name !='windy_cliff_grid': ax.set_yticklabels( ["%d"% y for y in np.arange(0, env.dim_y*env.dim_x, env.dim_x)][::-1])return imdef plot_rewards(n_episodes, rewards, average_range=10, ax=None):""" Generate plot showing total reward accumulated in each episode. """if ax isNone: fig, ax = plt.subplots() smoothed_rewards = (conv(rewards, np.ones(average_range), mode='same')/ average_range) ax.plot(range(0, n_episodes, average_range), smoothed_rewards[0:n_episodes:average_range], marker='o', linestyle='--') ax.set(xlabel='Episodes', ylabel='Total reward')def plot_performance(env, value, reward_sums): fig, axes = plt.subplots(nrows=2, ncols=2, figsize=(16, 12)) plot_state_action_values(env, value, ax=axes[0,0]) plot_quiver_max_action(env, value, ax=axes[0,1]) plot_rewards(n_episodes, reward_sums, ax=axes[1,0]) im = plot_heatmap_max_val(env, value, ax=axes[1,1]) fig.colorbar(im)#@title configuración de la figuraimport ipywidgets as widgets # interactive display%config InlineBackend.figure_format ='retina'plt.style.use("bmh")```
Este algortimo nos permite, a diferencia de e-greedy,no tener una exploración por medio una acción arbitraria escogida con una cierta probabilidad constante, este algoritmo cambia su balanceo de exploración-explotación cuando va recolectando más información del ambiente. Cambia de ser principalmente exploratorio a explotar mientras más información se tenga. El algoritmo esta represantado por:
: Es un valor de confianza que controla la exploración
: el valor estimado de la acción en el tiempo
: El numero de veces que esa acción ha sido seleccionada antes del tiempo
En UCB normal, no se asume ningún prior bayesiano en la dsitribución de recompensa y se usa la inequidad de Hoeffding para generalizar estimaciones. Si sabemos que forma tiene esta distribución, o podemos hacer una buena estimación, podremos hacer que los “bounds” también sean una mejor estimación.
Uno de los acercamientos más novedosos para resolver el problema, consiste en que a cada paso se selecciona una acción de acuerdo a una probabilidad “optima” :
𝟙
Siendo la probabilidad de tomar una acción dada la historia
Para este bandido en particular se asume un prior , con y de acuerdo a las veces que hemos tenido exito o fallado.
Primero se inicializan las variables de acuerdo con el nivel de confianza acerca de obtener la recompensa, y en cada tiempo se samplea una recompensa esperada de la distribución prior para cada acción, seleccionando la mejor. Después de observar la verdadera recompensa, se puede actualizar la distribución , que es basicamente inferencia Bayesiana, para poder computar la posterior con el prior y el likelihood.
𝟙𝟙
Todo esto viene de la idea de “probability matching”, cada probabilidad sampleada es equivalente a la probabilidad de que cada acción sea optima.