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　(√T)　regret.　In　this　paper,　we　study　MAB　and　SLB　with　quantum　reward　oracles　and　propose　quantum　algorithms　for　both　models　with　O(poly(log　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.　Copyright　©　2023,　Association　for　the　Advancement　of　Artificial　Intelligence　(www.aaai.org).　All　rights　reserved.