Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learning
This work provides a formal proof of concept for quantum advantage in reinforcement learning, addressing a foundational challenge for researchers in quantum computing and AI, though it is incremental as it builds on existing quantum algorithms.
The paper tackles the problem of improving sample complexity in reinforcement learning by developing a quantum policy iteration method that combines amplitude estimation and Grover search, showing that it can achieve quadratic efficiency gains over classical Monte Carlo methods in a simulated two-armed bandit MDP.
We present a full implementation and simulation of a novel quantum reinforcement learning method. Our work is a detailed and formal proof of concept for how quantum algorithms can be used to solve reinforcement learning problems and shows that, given access to error-free, efficient quantum realizations of the agent and environment, quantum methods can yield provable improvements over classical Monte-Carlo based methods in terms of sample complexity. Our approach shows in detail how to combine amplitude estimation and Grover search into a policy evaluation and improvement scheme. We first develop quantum policy evaluation (QPE) which is quadratically more efficient compared to an analogous classical Monte Carlo estimation and is based on a quantum mechanical realization of a finite Markov decision process (MDP). Building on QPE, we derive a quantum policy iteration that repeatedly improves an initial policy using Grover search until the optimum is reached. Finally, we present an implementation of our algorithm for a two-armed bandit MDP which we then simulate.