Algorithme UCB

Considérons un agent, qui à chaque instant, doit choisir une action (tester un médicament A, tester un médicament B, etc.). L'agent ne connaît pas l'effet des actions (par exemple, il ne sait pas si le médicament A est efficace, etc.). Après avoir exécuté une action, il observe son effet et reçoit une récompense (par exemple, il se rend compte que le médicament A soigne). L'algorithme UCB consiste à choisir l'action a à l'instant t qui maximise la quantité

${\displaystyle Q_{t}(a)+c{\sqrt {\frac {\log t}{N_{t}(a)}}}}$

où ${\displaystyle Q_{t}(a)}$ est la moyenne des récompenses obtenues en exécutant a, c est une constante, ${\displaystyle N_{t}(a)}$ est le nombre de fois que l'action a a été choisie jusqu'à l'instant t.

• Recherche arborescente Monte Carlo, qui utilise le même principe de choix pour explorer un arbre