Quantum bayesian reinforcement learning

Abstract

Reinforcement learning has had many recent achievements and is becoming increasingly more relevant in the scientific community. As such, this work uses quantum computing to find potential advantages over classical reinforcement learning algorithms, using Bayesian networks to model the considered decision making environments. For this purpose, this work makes use of quantum rejection sampling, a quantum approximate inference algorithm for Bayesian networks proposed by Low et al. [2014] with a quadratic speedup over its classical counterpart for sparse networks. It is shown that this algorithm can only provide quantum speedups for partially observable environments, and a quantum-classical hybrid lookahead al gorithm is presented to solve these kinds of problems. Moreover, this work also includes both sample and computational complexity analysis of both this quantum lookahead algorithm and its classical alternative. While the sample complexity is shown to be identical for both algorithms, the quantum approach provides up to a quadratic speedup in computational complexity. Finally, the potential advantages of this new algo rithm are experimentally tested in different small experiments. The results show that this speedup can be leveraged either to improve the rational decision-making skills of agents or to reduce their decision-making time due to the reduction in computational complexity.

A aprendizagem por reforço tem recentemente alcançado muito sucesso e a tornar-se cada vez mais relevante na comunidade científica. Este trabalho tira proveito da computação quântica para encontrar potenciais vantagens do seu uso comparativamente a algoritmos clássicos de aprendizagem de reforço. Nesta procura por vantagens, são utilizadas redes Bayesianas para modelar os ambientes de tomada de decisão considerados. Para este propósito, é utilizado o algoritmo de quantum rejection sampling, um algoritmo para inferência aproximada em redes Bayesianas proposto por Low et al. [2014] com um speedup quadrático comparativamente ao equivalente clássico para redes esparsas. É mostrado que este algoritmo quântico de inferência apenas tem vantagem na sua aplicação a ambientes parcialmente ob serváveis, e é apresentado um algoritmo híbrido clássico-quântico de lookahead para resolver este tipo de problemas. Para além disto, é também incluída uma análise da complexidade de amostragem e complex idade computacional de ambos os algoritmos. Enquanto a complexidade de amostragem é idêntica para as duas abordagens, o algoritmo quântico apresenta um speedup na complexidade computacional que é quadrático no melhor dos casos. Por fim, as potenciais vantagens deste novo algoritmo são testadas em experiências de pequena dimensão. Os resultados mostram que este speedup pode ser utilizado tanto para melhorar a capacidade de tomada de decisão de agentes como para diminuir o tempo de tomada de decisão dos mesmos devido à redução da complexidade computacional.