Algorithme UCB
En intelligence artificielle, plus précisément en apprentissage par renforcement, l'algorithme UCB (pour Upper Confidence Bounds) est une stratégie pour le problème du bandit manchot, qui consiste à exploiter les choix fructueux et à explorer les choix peu explorées jusqu'à présent. Il a été proposé par P. Auer en 2002 [1].
Principe[modifier | modifier le code]
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é
où est la moyenne des récompenses obtenues en exécutant a, c est une constante, est le nombre de fois que l'action a a été choisie jusqu'à l'instant t.
Cette algorithme possède une complexité temporelle maximale :
Exemple[modifier | modifier le code]
Extensions[modifier | modifier le code]
L'algorithme PUCT est une variante de cette stratégie, il permet d'améliorer la complexité temporelle maximale grâce à un entrainement préalablement effectué sur un jeu de donné similaire. Cet algorithme est notamment utilisé dans le programme d'échec Leela Chess Zero[3], ou sous une version modifiée dans AlphaZero[4].
Voir aussi[modifier | modifier le code]
- Recherche arborescente Monte Carlo, qui utilise le même principe de choix pour explorer un arbre
Notes et références[modifier | modifier le code]
- Auer, P., Cesa-Bianchi, N. & Fischer, P. Machine Learning (2002) 47: 235.
- « Finite-time Analysis of the Multiarmed Bandit Problem », Machine Language, vol. 47, , p. 235–256
- « Technical Explanation of Leela Chess Zero »
- « Mastering the game of Go with deep neural networks and tree search », Nature, no 529, , p. 484–489
