Report
Quantum Algorithms for Reinforcement Learning with a Generative Model
| العنوان: | Quantum Algorithms for Reinforcement Learning with a Generative Model |
|---|---|
| المؤلفون: | Wang, Daochen, Sundaram, Aarthi, Kothari, Robin, Kapoor, Ashish, Roetteler, Martin |
| المصدر: | Proceedings of the 38th International Conference on Machine Learning, PMLR 139:10916-10926, 2021 |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics, Computer Science - Machine Learning |
| الوصف: | Reinforcement learning studies how an agent should interact with an environment to maximize its cumulative reward. A standard way to study this question abstractly is to ask how many samples an agent needs from the environment to learn an optimal policy for a $\gamma$-discounted Markov decision process (MDP). For such an MDP, we design quantum algorithms that approximate an optimal policy ($\pi^*$), the optimal value function ($v^*$), and the optimal $Q$-function ($q^*$), assuming the algorithms can access samples from the environment in quantum superposition. This assumption is justified whenever there exists a simulator for the environment; for example, if the environment is a video game or some other program. Our quantum algorithms, inspired by value iteration, achieve quadratic speedups over the best-possible classical sample complexities in the approximation accuracy ($\epsilon$) and two main parameters of the MDP: the effective time horizon ($\frac{1}{1-\gamma}$) and the size of the action space ($A$). Moreover, we show that our quantum algorithm for computing $q^*$ is optimal by proving a matching quantum lower bound. Comment: 26 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2112.08451 |
| رقم الانضمام: | edsarx.2112.08451 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |