Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/86205
Título: | Quantum bayesian reinforcement learning |
Autor(es): | Cunha, Gilberto Rui Nogueira |
Orientador(es): | Barbosa, L. S. Sequeira, André Manuel Resende Oliveira, Michael |
Palavras-chave: | Reinforcement learning Bayesian networks Quantum computing Quantum decision-making Aprendizagem por reforço Redes Bayesianas Computação quântica Tomada de decisão quântica |
Data: | 10-Jan-2023 |
Resumo(s): | 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. |
Tipo: | Dissertação de mestrado |
Descrição: | Dissertação de mestrado em Engineering Physics |
URI: | https://hdl.handle.net/1822/86205 |
Acesso: | Acesso aberto |
Aparece nas coleções: | BUM - Dissertações de Mestrado DI - Dissertações de Mestrado |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Gilberto Rui Nogueira Cunha.pdf | Dissertação de Mestrado | 2,92 MB | Adobe PDF | Ver/Abrir |
Este trabalho está licenciado sob uma Licença Creative Commons