Utilize este identificador para citar ou criar um atalho para este documento:
https://hdl.handle.net/10923/18619
Tipo: | masterThesis |
Título: | Solving a markov decision process multidimensional problem with tensor decomposition |
Autor(es): | Kuinchtner, Daniela |
Orientador: | Sales, Afonso Henrique Corrêa de Meneguzzi, Felipe Rech |
Editora: | Pontifícia Universidade Católica do Rio Grande do Sul |
Programa: | Programa de Pós-Graduação em Ciência da Computação |
Data de Publicação: | 2021 |
Palavras-chave: | CADEIAS DE MARKOV - COMPUTAÇÃO SIMULAÇÃO E MODELAGEM EM COMPUTADORES INFORMÁTICA |
Resumo: | Processo de Decisão de Markov (MDP) é um modelo usado para planejamento de tomada de decisão de agentes em ambientes estocásticos e completamente observáveis. Embora, muita pesquisa se concentra na solução de problemas de MDPs atômicos em formas tabulares ou MDPs com representações fatoradas, nenhuma se baseia em métodos de decomposição de tensores. Resolver MDPs usando álgebra tensorial oferece a perspectiva de alavancar avanços em cálculos baseados em tensor para aumentar a eficiência de solucionadores de MDP. Nesta pesquisa, primeiro, é formalizado problemas multidimensionais de MDP usando álgebra tensorial. Segundo, é desenvolvido um solucionador de MDP usando o método de decomposição de tensor CANDECOMP-PARAFAC para compactar as matrizes de transição de estados. O solucionador utiliza os algoritmos de iteração de valor e iteração de política para computar a solução de forma compacta. Então, os algoritmos compactos são avaliados de forma empírica em comparação com métodos tabulares. Como resultados, é mostrado que a abordagem tensorial pode computar problemas maiores usando substancialmente menos memória, abrindo novas possibilidades para métodos baseadas em tensores para o planejamento estocástico. Markov Decision Process (MDP) is a model used for planning decision-making of agents in stochastic and completely observable environments. Although much research is focused on solving atomic MDP problems in tabular forms or MDP problems with factored representations, none is based on tensor decomposition methods. Solving MDPs using tensor algebra offers the prospect of leveraging advances in tensor-based calculations to increase MDP solvers’ efficiency. In this research, first, we formalize MDP multidimensional problems using tensor algebra. Second, we develop an MDP solver using the CANDECOMP-PARAFAC tensor decomposition method to compact state transition matrices. The solver uses the value iteration and policy iteration algorithms to compute the solution compactly. Then, we empirically evaluate the compact algorithms compared to tabular methods. As a result, we show that the tensor approach can compute larger problems using substantially less memory, opening up new possibilities for tensor-based methods for stochastic planning. |
URI: | https://hdl.handle.net/10923/18619 |
Aparece nas Coleções: | Dissertação e Tese
|
Todos os itens no Repositório da PUCRS estão protegidos por copyright, com todos os direitos reservados, e estão licenciados com uma Licença Creative Commons - Atribuição-NãoComercial 4.0 Internacional. Saiba mais.