A Quantum Enhanced Learning Algorithm for Maze Problems

Abstract

In reinforcement learning, a so-called agent should learn to optimally solve a given task by performing actions within an environment. As an example, we consider the grid-world, a two-dimensional maze for which the shortest way from an initial position to a given goal has to be found. The agent receives rewards for helpful actions which enables him to learn optimal solutions.

For large action spaces, a mapping of actions to a quantum setting can be beneficial in finding rewarded actions faster and thus in speeding up the learning process. This speed-up can be achieved by oracularizing the environment and performing amplitude amplification. Based on this technique, a hybrid agent which alternates between quantum and classical behavior has been developed previously for deterministic and strictly epochal environments. Here, strictly epochal means that an epoch consists of a fixed number of actions, after which the environment is reset to its initial state.

We present and analyze strategies which aim at resolving the hybrid agent’s current restriction of searching for action sequences with a fixed length. This is a first step towards applying the hybrid agent on environments with a generally unknown optimal action sequence length such as in the grid-world problem.