Algorithme optimal pour résoudre les problèmes de bandit à n bras?

13

Je l' ai lu sur un certain nombre d'algorithmes pour la résolution des problèmes de bandit n armés comme -greedy, softmax et UCB1, mais je vais avoir quelques problèmes de tri par quelle approche est la meilleure pour réduire au minimum le regret.ϵ

Existe-t-il un algorithme optimal connu pour résoudre le problème des bandits à n bras? Existe-t-il un choix d'algorithme qui semble fonctionner le mieux dans la pratique?

JS01
la source
Vraisemblablement, il n'y a pas de solution optimale reconnue, sinon la page Wikipédia le dirait et il n'y aurait pas de page Sourceforge
Henry
Cela ne devrait-il pas être sur l'informatique théorique SE?
1
@mbq puisque l'apprentissage par renforcement est une branche de l'apprentissage automatique, je ne pense pas;)
steffen
@steffen Bien sûr, le nom semblait "tcsy".
@mbq Je ne comprends pas. Que signifie "tscy"?
steffen

Réponses:

9

Voici deux documents d'enquête que j'ai trouvés récemment. Je ne les ai pas encore lus, mais les résumés semblent prometteurs.

Vannorel et Mehryar Mohri de Joann: Algorithmes de bandit à plusieurs bras et évaluation empirique (2005)

Du résumé:

Le problème des bandits à plusieurs bras pour un joueur est de décider quel bras d'une machine à sous K tirer pour maximiser sa récompense totale dans une série d'essais. De nombreux problèmes d'apprentissage et d'optimisation du monde réel peuvent être modélisés de cette manière. Plusieurs stratégies ou algorithmes ont été proposés comme solution à ce problème au cours des deux dernières décennies, mais, à notre connaissance, il n'y a pas eu d'évaluation commune de ces algorithmes.

Volodymyr Kuleshov et Doina Precup: Algorithmes pour le problème des bandits multi-armés (2000) Extrait du résumé:

Deuxièmement, les performances de la plupart des algorithmes varient considérablement avec les paramètres du problème des bandits. Notre étude identifie pour chaque algorithme les paramètres où il fonctionne bien et les paramètres où il fonctionne mal.

steffen
la source