Performance analysis of a hybrid agent for quantum-accessible reinforcement learning

Abstract

In the last decade quantum machine learning has provided fascinating and fundamental improvements to supervised, unsupervised and reinforcement learning. In reinforcement learning, a so-called agent is challenged to solve a task given by some environment. The agent learns to solve the task by exploring the environment and exploiting the rewards it gets from the environment. For some classical task environments, such as deterministic strictly epochal environments, an analogue quantum environment can be constructed which allows to find rewards quadratically faster by applying quantum algorithms. In this paper, we analytically analyze the behavior of a hybrid agent which combines this quadratic speedup in exploration with the policy update of a classical agent. This leads to a faster learning of the hybrid agent compared to the classical agent. We demonstrate that if the classical agent needs on average $⟨J⟩$ rewards and $⟨T{⟩}_c$ epochs to learn how to solve the task, the hybrid agent will take $⟨T{⟩}_q\le \alpha \sqrt{⟨T{⟩}_c⟨J⟩}$ epochs on average. Here, $\alpha$ denotes a constant which is independent of the problem size. Additionally, we prove that if the environment allows for maximally ${\alpha }_o{k}_{\text{max}}$ sequential coherent interactions, e.g. due to noise effects, an improvement given by $⟨T{⟩}_q\approx {\alpha }_o⟨T{⟩}_c/4k_{\text{max}}$ is still possible.

arXiv comment13 pages, 4 figures

References in corpus (18)

• Quantum Machine Learning
• Supervised learning with quantum enhanced feature spaces
• An introduction to quantum machine learning
• Tight bounds on quantum searching
• Quantum computers can search rapidly by using almost any transformation
• Quantum machine learning: a classical perspective
• Quantum-enhanced machine learning
• Fixed-point quantum search with an optimal number of queries
• Quantum speedup for active learning agents
• Experimental quantum speed-up in reinforcement learning agents
• Deterministic Grover search with a restricted oracle
• Quantum enhancements for deep reinforcement learning in large spaces
• Speeding-up the decision making of a learning agent using an ion trap quantum processor
• Photonic architecture for reinforcement learning
• Benchmarking projective simulation in navigation problems
• Classical and quantum regression analysis for the optoelectronic performance of NTCDA/p-Si UV photodiode
• Quantum Bandits
• Quantum-accessible reinforcement learning beyond strictly epochal environments

Cited by in corpus (1)

• Quantum Deep Reinforcement Learning for Robot Navigation Tasks