Reglas de Respuesta

Presentación

Video

Dilema de Exploración-Explotación

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 \(\color{blue}{\pi}\). También se necesita una función de valor por cada acción, al valor se le conoce como valor \(\color{green}{Q}\) . El valor \(\color{green}{Q}\) por tomar la acción \(\color{blue}{a \in A}\) en un tiempo determinado como \(t\) que no dará el valor de la recompensa en este tiempo \(r_t\) dada la acción elegida \(\color{blue}{a}\) . La fórmula es la siguiente:

\[\begin{align} \color{green}{Q}(\color{blue}{a}) = \mathbb{E} [\color{green}{r}_{t} | \color{blue}{a}_{t} = \color{blue}{a}] \end{align}\]

El objetivo sería el poder maximizar la recompensa la probabilidad optima de recompensa \[\theta^{}\] de la acción optima \[a^{}\] es:

\[\ \color{blue}{a_t}=\arg max_{a \in \mathcal{A}}\color{green}{Q}(\color{blue}{a})\]

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 - \(\epsilon\) para \(\epsilon \in [0,1]\) seleccionamos la opción con mayor valor o “greedy”, en caso contrario con una probabilidad pequeña \(\epsilon\) 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:

\[ \mathcal{L}_T = \text{E} \left[ \sum_{t=1}^T (\theta^* - Q(a_t)) \right] \]

Funciones para graficar y paqueterias.

Haz Clic para ver el Código

```{python}
# @title Funciones para graficar y paquetes
import time
import numpy as np
import matplotlib.pyplot as plt
from scipy.signal import convolve as conv
from scipy.stats import beta

np.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 in range(n_steps):
    action = choice_fn(q, epsilon,t,counts,asbeta,bsbeta,c)
    counts[action] += 1
    if np.random.random() < q[action]:
      reward=1
    else:
      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 is None:
    fig, ax = plt.subplots()
  for a in range(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 is None:
    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 is None:
    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 im

def plot_rewards(n_episodes, rewards, average_range=10, ax=None):
  """
  Generate plot showing total reward accumulated in each episode.
  """
  if ax is None:
    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 figura

import ipywidgets as widgets       # interactive display
%config InlineBackend.figure_format = 'retina'
plt.style.use("bmh")
```

Simulación.

Haz Clic para ver el Código

```{python}
def epsilon_greedy(q, epsilon,t,counts,asbeta,bsbeta,c):
  be_greedy = np.random.random()> epsilon
  if be_greedy:
    action = np.argmax(q)
  else:
    action = np.random.choice(len(q))
  return action

def UCB1(q, epsilon,t,counts,asbeta,bsbeta,c):
  action= max(range(len(q)),key=lambda x:q[x]+np.sqrt((2*np.log(t))/(1+counts[x])) )
  return action
def BayesianUCB(q, epsilon,t,counts,asbeta,bsbeta,c):
  action= max(
            range(len(q)),
            key=lambda x: asbeta[x] / float(asbeta[x] + bsbeta[x]) + beta.std(
                asbeta[x], bsbeta[x]) *c
        )
  return action

def ThompsonSampling(q, epsilon,t,counts,asbeta,bsbeta,c):
  samples= [np.random.beta(asbeta[x], bsbeta[x]) for x in range(len(q))]
  action= max(range(len(q)),key=lambda x: samples[x])
  return action

q = [0.01,0.89, 0.2, 0.8]
epsilon = 0.1

plot_choices(q, epsilon,epsilon_greedy ,c=1)

def explore_epilson_values(epsilon=0.1):
  q = [0.01,0.89, 0.2, 0.8]
  plot_choices(q, epsilon,epsilon_greedy ,c=3, rng_seed=None)
```

UCB Upper confidence Bound

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:

\(c\) : Es un valor de confianza que controla la exploración

\(Q_t(a)\): el valor estimado de la acción en el tiempo

\(N_t(a)\): El numero de veces que esa acción ha sido seleccionada antes del tiempo \((t)\)

\[A_t =\underset{a} {\arg \max} \left[ Q_t(a) + c \ \sqrt{\frac{\log t}{N_t(a)}} \right] \]

Haz Clic para ver el Código

```{python}
q = [0.01,0.89, 0.2, 0.8]
plot_choices(q, epsilon, UCB1,c=1)
```

Bayesian UCB

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.

Siendo este el algoritmo usado:

Haz Clic para ver el Código

```{python}
q = [0.01,0.89, 0.2, 0.8]
plot_choices(q, epsilon, BayesianUCB,c=1)
```

Thompson Sampling

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” \(\pi(a \vert h_t)\):

\[ \begin{aligned} \pi(a ; \vert ; h_t) &= \mathbb{P} [ Q(a) > Q(a'), \forall a' \neq a ; \vert ; h_t] \ &= \mathbb{E}{\mathcal{R} \vert h_t} [ \mathbb{1}(a = \arg\max{a \in \mathcal{A}} Q(a)) ] \end{aligned} \]

Siendo \(\pi(a \vert h_t)\) la probabilidad de tomar una acción dada la historia \(h_t\)

Para este bandido en particular se asume un prior \(Beta(\sigma,\beta)\), con \(\sigma\) y \(\beta\) 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 \(t\) se samplea una recompensa esperada \(Q(a)\) 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 \(Beta\), que es basicamente inferencia Bayesiana, para poder computar la posterior con el prior y el likelihood. \(a^{TS}t = \arg\max{a \in \mathcal{A}} \tilde{Q}(a)\)

\[ \begin{aligned} \alpha_i & \leftarrow \alpha_i + r_t \mathbb{1}[a^{TS}_t = a_i] \\ \beta_i & \leftarrow \beta_i + (1-r_t) \mathbb{1}[a^{TS}_t = a_i] \end{aligned} \]

Todo esto viene de la idea de “probability matching”, cada probabilidad sampleada es equivalente a la probabilidad de que cada acción sea optima.

Haz Clic para ver el Código

```{python}
q = [0.01,0.89, 0.2, 0.8]
plot_choices(q, epsilon, ThompsonSampling,c=1)
```

Simulación Bandidos Multibrazo

Haz Clic para ver el Código

```{python}
def Bernoulli_multi_armed_bandit(n_arms, epsilon, alpha, n_steps,c,choice_fn,init_a=1,init_b=1, probas=None):
 
  q = np.zeros(n_arms)
  q2 = np.zeros(n_arms)
  qs = np.zeros((n_steps, n_arms))
  qs2 = np.zeros((n_steps, n_arms))
  counts = np.zeros_like(q)
  rewards = np.zeros(n_steps)
  actions = np.zeros(n_steps)
  optimal = np.zeros(n_steps)
  counts = np.zeros_like(q)
  asbeta = [init_a]*len(q)
  bsbeta = [init_b]*len(q)
  regret=0
  regrets =[0.] 
  total_reward=0
  avg_reward =[]
  times=0
  mu=0
  if probas is None:
    np.random.seed(int(time.time()))
    qprobas = [np.random.random() for _ in range(len(q))]
  else:
    qprobas = probas
  for t in range(n_steps):
    times+=1
    action = choice_fn(q, epsilon,t,counts,asbeta,bsbeta,c)
    actions[t] = action
    counts[action] += 1

    if np.random.random() < qprobas[action]:
      reward=1
    else:
      reward=0

    rewards[t]=reward  
    total_reward += reward
    avg_reward.append(total_reward/times)  
 
    optimal_action = np.argmax(qprobas)
    optimal[t] = action == optimal_action
    regret+= qprobas[optimal_action] - qprobas[action]
    regrets.append(regret)

 
    q[action] = q[action] + alpha * (reward - q[action])
    qs[t] = q
    asbeta[action] += reward
    bsbeta[action] += (1 - reward)

  results = {
      'qs': qs,
      'qs2': qs2,
      'actions': actions,
      'rewards': rewards,
      'mu': mu,
      'optimal': optimal,
      'regrets':regrets,
      'choice_fn':choice_fn,
      'qprobas':qprobas,
      'optimal_action':optimal_action,
      'avg_reward':avg_reward
  }

  return results

np.random.seed(1)

n_arms = 10
epsilon = 0.1
alpha = 0.01
n_steps = 1000
c=3
choice_fn=epsilon_greedy

results = Bernoulli_multi_armed_bandit(n_arms, epsilon, alpha, n_steps,c,choice_fn)

fig = plt.figure(figsize=(20, 13))
fig.subplots_adjust(bottom=0.3, wspace=0.3)
ax1 = fig.add_subplot(131)
ax2 = fig.add_subplot(132)
ax1.plot(range(len(results['regrets'])),results['regrets'], label='epsilon_greedy' )
ax2.plot(range(len(results['avg_reward'])), results['avg_reward'], label= 'epsilon_greedy')
ax1.set_xlabel('Time step',fontsize = 30, fontweight ='bold')
ax1.set_ylabel('Regret acumulado',fontsize = 30, fontweight ='bold')
ax1.legend(fontsize=20)
ax1.grid('k', ls='--', alpha=0.3)
ax2.set_xlabel("n_iter",fontsize = 30, fontweight ='bold')
ax2.set_ylabel("Recompensa Promedio",fontsize = 30, fontweight ='bold')
ax2.grid('k', ls='--', alpha=0.3)
ax2.legend(fontsize=20)
plt.show()
```

Elecciones

Haz Clic para ver el Código

```{python}
choice_fn=UCB1

results = Bernoulli_multi_armed_bandit(n_arms, epsilon, alpha, n_steps,c,choice_fn)

fig = plt.figure(figsize=(20, 13))
fig.subplots_adjust(bottom=0.3, wspace=0.3)
ax1 = fig.add_subplot(131)
ax2 = fig.add_subplot(132)
ax1.plot(range(len(results['regrets'])),results['regrets'], label='UCB1' )
ax2.plot(range(len(results['avg_reward'])), results['avg_reward'], label= 'UCB1')
ax1.set_xlabel('Time step',fontsize = 30, fontweight ='bold')
ax1.set_ylabel('Regret acumulado',fontsize = 30, fontweight ='bold')
ax1.legend(fontsize=20)
ax1.grid('k', ls='--', alpha=0.3)
ax2.set_xlabel("n_iter",fontsize = 30, fontweight ='bold')
ax2.set_ylabel("Recompensa Promedio",fontsize = 30, fontweight ='bold')
ax2.grid('k', ls='--', alpha=0.3)
ax2.legend(fontsize=20)

plt.show()
```

Recompensa

Haz Clic para ver el Código

```{python}
choice_fn=BayesianUCB

results = Bernoulli_multi_armed_bandit(n_arms, epsilon, alpha, n_steps,c,choice_fn)

fig = plt.figure(figsize=(20, 13))
fig.subplots_adjust(bottom=0.3, wspace=0.3)
ax1 = fig.add_subplot(131)
ax2 = fig.add_subplot(132)
ax1.plot(range(len(results['regrets'])),results['regrets'], label='BayesianUCB' )
ax2.plot(range(len(results['avg_reward'])), results['avg_reward'], label= 'BayesianUCB')
ax1.set_xlabel('Time step',fontsize = 30, fontweight ='bold')
ax1.set_ylabel('Regret Acumulado',fontsize = 30, fontweight ='bold')
ax1.legend(fontsize=20)
ax1.grid('k', ls='--', alpha=0.3)
ax2.set_xlabel("n_iter",fontsize = 30, fontweight ='bold')
ax2.set_ylabel("Recompensa Promedio",fontsize = 30, fontweight ='bold')
ax2.grid('k', ls='--', alpha=0.3)
ax2.legend(fontsize=20)
plt.show()
```

Otro algorítmo

Haz Clic para ver el Código

```{python}
choice_fn=ThompsonSampling

results = Bernoulli_multi_armed_bandit(n_arms, epsilon, alpha, n_steps,c,choice_fn)

fig = plt.figure(figsize=(20, 13))
fig.subplots_adjust(bottom=0.3, wspace=0.3)
ax1 = fig.add_subplot(131)
ax2 = fig.add_subplot(132)
ax1.plot(range(len(results['regrets'])),results['regrets'], label='ThompsonSampling' )
ax2.plot(range(len(results['avg_reward'])), results['avg_reward'], label= 'ThompsonSampling')
ax1.set_xlabel('Time step',fontsize = 30, fontweight ='bold')
ax1.set_ylabel('Regret Acumulado',fontsize = 30, fontweight ='bold')
ax1.legend(fontsize=20)
ax1.grid('k', ls='--', alpha=0.3)
ax2.set_xlabel("n_iter",fontsize = 30, fontweight ='bold')
ax2.set_ylabel("Recompensa Promedio",fontsize = 30, fontweight ='bold')
ax2.grid('k', ls='--', alpha=0.3)
ax2.legend(fontsize=20)
plt.show()
```

Comparación.

Haz Clic para ver el Código

```{python}
def plot_bandit_solutions(soluciones,n_arms,epsilon,alpha,n_steps,c,names):
  np.random.seed(1)
  fig = plt.figure(figsize=(20, 13))
  fig.subplots_adjust(bottom=0.3, wspace=0.3)
  ax1 = fig.add_subplot(131)
  ax2 = fig.add_subplot(132)
  f=0
  for i in soluciones:
    choice_fn= soluciones[f]
    results = Bernoulli_multi_armed_bandit(n_arms, epsilon, alpha, n_steps,c,choice_fn)
    ax1.plot(range(len(results['regrets'])),results['regrets'], label= names[f])
    ax2.plot(range(len(results['avg_reward'])), results['avg_reward'], label= names[f])
    f+=1
  ax1.set_xlabel('Time step',fontsize = 30, fontweight ='bold')
  ax1.set_ylabel('Regret Acumulado',fontsize = 30, fontweight ='bold')
  ax1.legend(fontsize=20)
  ax1.grid('k', ls='--', alpha=0.3)
  ax2.set_xlabel("n_iter",fontsize = 30, fontweight ='bold')
  ax2.set_ylabel("Recompensa Promedio",fontsize = 30, fontweight ='bold')
  ax2.grid('k', ls='--', alpha=0.3)
  ax2.legend(fontsize=20)
  plt.show()

n_arms = 10
epsilon = 0.1
alpha = 0.1
n_steps = 1000
c=3
soluciones= [epsilon_greedy,UCB1,BayesianUCB,ThompsonSampling]
names=['epsilon_greedy','UCB1','BayesianUCB','ThompsonSampling']
plot_bandit_solutions(soluciones,n_arms,epsilon,alpha,n_steps,c,names)
```

Versión Interactiva.

Aquí puedes encontrar la versión interactiva.