L’algorithme de la borne supérieure de confiance (UCB) est une approche populaire et efficace pour résoudre le problème du bandit manchot. Il offre des garanties mathématiques solides de convergence rapide, optimisant ainsi le processus d’exploration.

Malgré son efficacité pour résoudre le problème du MAB, l’algorithme UCB présente certaines limitations notables qui restreignent son application dans le domaine plus large de l’apprentissage par renforcement :

• Hypothèse de récompenses stationnaires : l’algorithme UCB suppose que les distributions de récompenses ne changent pas au fil du temps ;
• Contraintes sur les espaces d’états et d’actions : pour commencer à choisir des actions selon une certaine logique, l’algorithme UCB exige d’essayer chaque action dans chaque état au moins une fois.

Bien que la première limitation puisse être contournée en modifiant légèrement l’algorithme, la seconde limitation demeure un défi majeur dans de nombreuses applications pratiques.

Fonctionnement

L’algorithme UCB équilibre exploration et exploitation en attribuant un intervalle de confiance à la valeur estimée de chaque action et en sélectionnant l’action avec la borne supérieure la plus élevée. Cette approche garantit que les actions aux récompenses incertaines sont explorées tout en privilégiant celles qui semblent optimales.

Les étapes de l'algorithme UCB sont identiques à celles de l'algorithme epsilon-greedy, à l'exception de l'étape de sélection d'une action. L'algorithme UCB sélectionne une action $A_t$ à l'instant $t$ en utilisant la formule suivante :

où :

• $Q_t(a)$ est la récompense estimée de l'action $a$ à l'instant $t$ ;
• $N_t(a)$ est le nombre de fois que l'action $a$ a été sélectionnée jusqu'à l'instant $t$ ;
• $c > 0$ est un paramètre ajustable qui contrôle l'équilibre entre exploration et exploitation, similaire à $\varepsilon$ dans l'algorithme $\varepsilon$-greedy ;
• $\ln$ est la fonction logarithme naturel ;
• $\argmax$ est la valeur de l'argument ($a$, dans ce cas) qui maximise l'expression.

Intuition

$\argmax$ choisit l'action qui maximise la somme de deux parties : la valeur estimée de l'action et un intervalle de confiance. L'intervalle de confiance est multiplié par un facteur $c$, où des valeurs plus grandes rendent l'intervalle plus large, ce qui signifie que l'agent est moins confiant quant à la valeur de l'action, ce qui favorise l'exploration.

La taille de cet intervalle de confiance dépend de deux facteurs :

1. Temps : plus le temps passe, moins l'agent est confiant dans la valeur de l'action ;
2. Fréquence de l'action : plus une action est choisie fréquemment, plus l'agent est confiant dans sa valeur.

Exemple de code

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]

Informations supplémentaires

L'algorithme UCB intègre un mécanisme d'exploration, nécessitant un réglage minutieux de l'hyperparamètre $c$ pour fonctionner efficacement. La valeur optimale de $c$ varie selon le problème spécifique. Voici quelques recommandations générales :

• Forte variance des récompenses : une valeur de $c$ plus élevée garantit une exploration suffisante ;
• Récompenses stables : une valeur de $c$ plus faible permet à l'algorithme de se concentrer rapidement sur l'action optimale ;
• Valeur par défaut courante : un point de départ typique est $c = 1$, mais un ajustement expérimental est souvent nécessaire pour obtenir les meilleurs résultats.

Résumé

L'algorithme UCB est une méthode puissante et rigoureuse pour équilibrer l'exploration et l'exploitation dans les problèmes de bandit manchot. En sélectionnant les actions sur la base des récompenses estimées et de l'incertitude, il garantit un apprentissage efficace tout en minimisant le regret.