Quantum greedy algorithms for multi-armed bandits

Multi-armed bandits are widely used in machine learning applications such as recommendation systems. Here, we implement two quantum versions of the e-greedy algorithm, a popular algorithm for multi-armed bandits. One of the quantum greedy algorithms uses a quantum maximization algorithm and the other is a simple algorithm that uses an amplitude encoding method as a quantum subroutine instead of the argmax operation in the e-greedy algorithm. For the former algorithm, given a quantum oracle, the query complexity is on the order root K (O(root K)) in each round, where K is the number of arms. For the latter algorithm, quantum parallelism is achieved by the quantum superposition of the arms and the run-time complexity is on the order O(K)/O(log K) in each round. Bernoulli reward distributions and the MovieLens dataset are used to evaluate the algorithms with their classical counterparts. The experimental results show that for best arm identification, the performance of the quantum greedy algorithm is comparable with that of the classical counterparts.