Al tratar con problemas de multi-armed bandits, los métodos tradicionales como epsilon-greedy y UCB estiman los valores de acción para decidir qué acción tomar. Sin embargo, los gradient bandits adoptan un enfoque diferente: aprenden preferencias por las acciones en lugar de estimar sus valores. Estas preferencias se ajustan con el tiempo utilizando ascenso estocástico por gradiente.

Preferencias

En lugar de mantener estimaciones de valor de acción $Q(a)$, los gradient bandits mantienen valores de preferencia $H(a)$ para cada acción $a$. Estas preferencias se actualizan utilizando un enfoque de ascenso estocástico por gradiente para maximizar las recompensas esperadas. La probabilidad de cada acción se calcula usando una función softmax:

donde:

• $H_t(a)$ es la preferencia por la acción $a$ en el paso de tiempo $t$;
• $P(A_t = a)$ es la probabilidad de seleccionar la acción $a$ en el paso de tiempo $t$;
• El denominador asegura que las probabilidades sumen 1.

Softmax es una función crucial en ML, utilizada comúnmente para convertir listas de números reales en listas de probabilidades. Esta función actúa como una aproximación suave a la función $\argmax$, permitiendo una exploración natural al otorgar a las acciones de menor preferencia una probabilidad distinta de cero de ser seleccionadas.

Regla de actualización

Después de seleccionar una acción $A_t$ en el tiempo $t$, los valores de preferencia se actualizan utilizando la siguiente regla:

donde:

• $\alpha$ es el tamaño del paso;
• $R_t$ es la recompensa recibida;
• $\bar R_t$ es la recompensa promedio observada hasta ahora.

Intuición

En cada paso de tiempo, todas las preferencias se ajustan ligeramente. El ajuste depende principalmente de la recompensa recibida y la recompensa promedio, y puede explicarse de la siguiente manera:

• Si la recompensa recibida es mayor que la promedio, la acción seleccionada se vuelve más preferida y las demás acciones se vuelven menos preferidas;
• Si la recompensa recibida es menor que la promedio, la preferencia de la acción seleccionada disminuye, mientras que las preferencias de las otras acciones aumentan, fomentando la exploración.

Código de ejemplo

def softmax(x):
  """Simple softmax implementation"""
  return np.exp(x) / np.sum(np.exp(x))

class GradientBanditsAgent:
  def __init__(self, n_actions, alpha):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.alpha = alpha # alpha
    self.H = np.zeros(n_actions) # Preferences
    self.reward_avg = 0 # Average reward
    self.t = 0 # Time step counter

  def select_action(self):
    """Select an action according to the gradient bandits strategy"""
    # Compute probabilities from preferences with softmax
    probs = softmax(self.H)
    # Choose an action according to the probabilities
    return np.random.choice(self.n_actions, p=probs)

  def update(self, action, reward):
    """Update preferences"""
    # Increase the time step counter
    self.t += 1
    # Update the average reward
    self.reward_avg += reward / self.t

    # Compute probabilities from preferences with softmax
    probs = softmax(self.H) # Getting action probabilities from preferences

    # Update preference values using stochastic gradient ascent
    self.H -= self.alpha * (reward - self.reward_avg) * probs
    self.H[action] += self.alpha * (reward - self.reward_avg)

Información adicional

Los gradient bandits presentan varias propiedades interesantes:

• Relatividad de las preferencias: los valores absolutos de las preferencias de acción no afectan el proceso de selección de acciones; solo importan sus diferencias relativas. Desplazar todas las preferencias por la misma constante (por ejemplo, sumando 100) resulta en la misma distribución de probabilidad;
• Efecto de la línea base en la regla de actualización: aunque la fórmula de actualización normalmente incluye la recompensa promedio como línea base, este valor puede ser reemplazado por cualquier constante que sea independiente de la acción elegida. La línea base influye en la velocidad de convergencia, pero no altera la solución óptima;
• Impacto del tamaño del paso: el tamaño del paso debe ajustarse según la tarea. Un tamaño de paso menor asegura un aprendizaje más estable, mientras que un valor mayor acelera el proceso de aprendizaje.

Resumen

Los bandits de gradiente ofrecen una alternativa poderosa a los algoritmos tradicionales de bandit al aprovechar el aprendizaje basado en preferencias. Su característica más interesante es la capacidad de equilibrar de forma natural la exploración y la explotación.