Upper Confidence Bound (UCB)

L’Upper Confidence Bound (UCB) est une stratégie utilisée dans les problèmes de bandits manchots (multi-armed bandit). L’idée principale est d’explorer les actions incertaines, mais aussi d’exploiter celles qui semblent les plus prometteuses. L’UCB fonctionne en équilibrant l’exploration et l’exploitation en fonction de la confiance que l’on a dans les estimations de récompenses.

L’algorithme choisit l’action ayant la plus grande borne supérieure de confiance, calculée en ajoutant à la moyenne des récompenses de l’action une marge qui diminue à mesure que le nombre d’essais de cette action augmente. Cela incite l’algorithme à explorer les actions qui ont été moins testées, tout en continuant à exploiter les actions qui ont eu de bons résultats.

Formule de l’UCB :

La règle pour sélectionner l’action $a_t$ à chaque étape est la suivante :

$$a_t = \arg\max_{a} \left( \hat{\mu}_a + \sqrt{\frac{2 \ln t}{n_a}} \right)$$

Où :

• $\hat{\mu}_a$ est la moyenne des récompenses obtenues pour l’action $a$.

• $n_a$ est le nombre de fois que l’action $a$ a été choisie.

• $t$ est le nombre total de tours (ou itérations).

• Le terme $\sqrt{\frac{2 \ln t}{n_a}}$ est la borne de confiance qui encourage l’exploration des actions moins souvent testées.