El algoritmo de límite superior de confianza (UCB) es un enfoque popular y eficaz para resolver el problema del multi-armed bandit. Ofrece fuertes garantías matemáticas de convergencia rápida, optimizando el proceso de exploración.

A pesar de su eficacia para resolver el problema MAB, el algoritmo UCB presenta algunas limitaciones notables que restringen su aplicación en el aprendizaje por refuerzo en general:

• Suposición de recompensas estacionarias: el algoritmo UCB asume que las distribuciones de recompensas no cambian con el tiempo;
• Restricciones en los espacios de estados y acciones: para comenzar a elegir acciones según cierta lógica, el algoritmo UCB requiere probar cada acción en cada estado al menos una vez.

Mientras que la primera limitación puede abordarse modificando ligeramente el algoritmo, la segunda limitación sigue siendo un desafío significativo en muchas aplicaciones prácticas.

Cómo funciona

El algoritmo UCB equilibra la exploración y la explotación asignando un intervalo de confianza al valor estimado de cada acción y seleccionando la acción con el mayor límite superior. Este enfoque garantiza que se exploren acciones con recompensas inciertas mientras se favorecen aquellas que parecen ser óptimas.

Los pasos del algoritmo UCB son idénticos a los pasos del algoritmo epsilon-greedy, excepto por el paso de selección de acción. El algoritmo UCB selecciona una acción $A_t$ en el instante de tiempo $t$ utilizando la siguiente fórmula:

donde:

• $Q_t(a)$ es la recompensa estimada de la acción $a$ en el tiempo $t$;
• $N_t(a)$ es el número de veces que la acción $a$ ha sido seleccionada hasta el tiempo $t$;
• $c > 0$ es un parámetro ajustable que controla el equilibrio entre exploración y explotación, similar a $\varepsilon$ en el algoritmo $\varepsilon$-greedy;
• $\ln$ es la función logaritmo natural;
• $\argmax$ es el valor del argumento ($a$, en este caso) que maximiza la expresión.

Intuición

$\argmax$ elige la acción que maximiza la suma de dos partes: el valor estimado de la acción y un intervalo de confianza. El intervalo de confianza está escalado por un factor $c$, donde valores mayores hacen que el intervalo sea más amplio, lo que significa que el agente está menos seguro sobre el valor de la acción, lo que fomenta la exploración.

El tamaño de este intervalo de confianza depende de dos factores:

1. Tiempo: a medida que pasa más tiempo, el agente se vuelve menos seguro sobre el valor de la acción;
2. Frecuencia de la acción: cuanto más a menudo se elige una acción, más seguro está el agente sobre su valor.

Código de ejemplo

class UpperConfidenceBoundAgent:
  def __init__(self, n_actions, confidence):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.confidence = confidence # c
    self.Q = np.zeros(self.n_actions) # Estimated action values
    self.N = np.zeros(self.n_actions) # Action selection counters
    self.t = 0 # Time step counter

  def select_action(self):
    """Select an action according to the upper confidence bound strategy"""
    # Increase the time step counter
    self.t += 1

    # Each action should be taken at least once
    for action in range(self.n_actions):
      if self.N[action] == 0:
        return action

    # Return the action with highest upper confidence bound
    return np.argmax(self.Q + self.confidence * np.sqrt(np.log(self.t) / self.N))

  def update(self, action, reward):
    """Update the values using sample average estimate"""
    # Increasing the action selection counter
    self.N[action] += 1
    # Updating the estimated action value
    self.Q[action] += (reward - self.Q[action]) / self.N[action]

Información adicional

El algoritmo UCB incorpora un mecanismo de exploración, que requiere un ajuste cuidadoso del hiperparámetro $c$ para funcionar de manera efectiva. El valor óptimo de $c$ varía según el problema específico. A continuación, se presentan algunas pautas generales:

• Alta varianza en las recompensas: un valor de $c$ más grande garantiza una exploración suficiente;
• Recompensas estables: un valor de $c$ más pequeño permite que el algoritmo se enfoque rápidamente en la acción óptima;
• Valor predeterminado común: un punto de partida típico es $c = 1$, pero a menudo requiere ajuste experimental para obtener los mejores resultados.

Resumen

El algoritmo UCB es un método sólido y eficaz para equilibrar la exploración y la explotación en problemas de multi-armed bandit. Al seleccionar acciones basándose tanto en las recompensas estimadas como en la incertidumbre, garantiza un aprendizaje eficiente mientras minimiza el arrepentimiento.