Multi-Armed Bandits and Quantum Channel Oracles
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909550389493760 |
|---|---|
| author | Buchholz, Simon Kübler, Jonas M. Schölkopf, Bernhard |
| author_facet | Buchholz, Simon Kübler, Jonas M. Schölkopf, Bernhard |
| contents | Multi-armed bandits are one of the theoretical pillars of reinforcement learning. Recently, the investigation of quantum algorithms for multi-armed bandit problems was started, and it was found that a quadratic speed-up (in query complexity) is possible when the arms and the randomness of the rewards of the arms can be queried in superposition. Here we introduce further bandit models where we only have limited access to the randomness of the rewards, but we can still query the arms in superposition. We show that then the query complexity is the same as for classical algorithms. This generalizes the prior result that no speed-up is possible for unstructured search when the oracle has positive failure probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_08544 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Multi-Armed Bandits and Quantum Channel Oracles Buchholz, Simon Kübler, Jonas M. Schölkopf, Bernhard Quantum Physics Machine Learning 68Q12 Multi-armed bandits are one of the theoretical pillars of reinforcement learning. Recently, the investigation of quantum algorithms for multi-armed bandit problems was started, and it was found that a quadratic speed-up (in query complexity) is possible when the arms and the randomness of the rewards of the arms can be queried in superposition. Here we introduce further bandit models where we only have limited access to the randomness of the rewards, but we can still query the arms in superposition. We show that then the query complexity is the same as for classical algorithms. This generalizes the prior result that no speed-up is possible for unstructured search when the oracle has positive failure probability. |
| title | Multi-Armed Bandits and Quantum Channel Oracles |
| topic | Quantum Physics Machine Learning 68Q12 |
| url | https://arxiv.org/abs/2301.08544 |