Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets
Rattachement africain : cn. Niveau de preuve : code pays fourni par la source.
Le résumé fourni par la source
Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horizon T suffer from the regret of at least the square root of T. In this paper, we study MAB and SLB with quantum reward oracles and propose quantum algorithms for both models with the order of the polylog T regrets, exponentially improving the dependence in terms of T. To the best of our knowledge, this is the first provable quantum speedup for regrets of bandit problems and in general exploitation in reinforcement learning. Compared to previous literature on quantum exploration algorithms for MAB and reinforcement learning, our quantum input model is simpler and only assumes quantum oracles for each individual arm.
Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.
Le contrôle bibliographique ouvert
DOI retrouvé dans Crossref DOI retrouvé ; titre concordant.
- Titre Crossref
- Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets
- Date Crossref
- 26/06/2023
- Éditeur
- Association for the Advancement of Artificial Intelligence (AAAI)
- Type
- journal-article
Ce recoupement confirme des métadonnées liées au DOI. Il ne confirme ni la méthode ni les conclusions de l’étude, et il ne compte pas comme une seconde source scientifique indépendante.
Où se fait cette recherche
-
Institute of Computing Technology pays non établi dans la noticeStructure de recherche
-
University of Chinese Academy of Sciences Institute of Computing Technology pays non établi dans la noticeUniversité ou école supérieure
-
Fuzhou University pays non établi dans la noticeUniversité ou école supérieure
-
Peking University pays non établi dans la noticeUniversité ou école supérieure
Institute of Computing Technology, Institute of Computing Technology — University of Chinese Academy of Sciences et Fuzhou University, avec 1 autre affiliation.
Une affiliation ne permet pas de déduire la nationalité d’un auteur.