André da Motta Salles Barreto
Resumo
Os problemas de tomada de decisão seqüencial envolvem uma série de escolhas sucessivas cujos efeitos podem se estender indefinidamente pelo futuro. Trata-se de um paradigma genérico que engloba desde tarefas simples do dia-a-dia até desafios enfrentados pela indústria. Uma maneira de solucionar esse tipo de problema é modelá-lo como um processo de decisão de Markov (MDP). Uma vez que um modelo formal do problema esteja disponível, pode-se recorrer à programação dinâmica ou à aprendizagem por reforço para determinar uma política de decisão ótima. No entanto, essas abordagens sofrem de uma séria questão de escalabilidade: problemas de tomada de decisão com um número razoavelmente grande de estados podem inviabilizá-las na prática, devido ao seu alto custo computacional. Uma forma de contornar essa questão é criar um modelo compacto do MDP. A abordagem apresentada neste trabalho, chamada fatoração estocástica, é uma proposta nesse sentido. A fatoração estocástica é a formalização de uma idéia bastante intuitiva: pode-se reduzir consideravelmente a dimensão de um MDP simplesmente redirecionando as suas transições para “estados arquetípicos” que representem bem a sua dinâmica. Resolvendo o problema no modelo reduzido, é possível encontrar uma política de decisão em uma pequena fração do tempo que levaria a solução do MDP original. O desempenho das políticas retornadas depende unicamente da qualidade da fatoração: em particular, uma fatoração estocástica exata leva garantidamente a uma das soluções ótimas do problema. Para demonstrar a efetividade desta abordagem na prática, os algoritmos derivados da fatoração estocástica são comparados com outras técnicas de programação dinâmica e aprendizagem por reforço em problemas de controle simples.
Abstract
In a sequential decision-making problem the consequences of a decision may last for an arbitrarily long time. This framework is generic enough to encompass tasks ranging from simple every-day-life decisions to complex challenges faced in industrial settings. One way to solve this kind of problem is to use a Markov decision process (MDP) as a model of the task. Once a formal description of the problem is available, dynamic programming and reinforcement-learning techniques may be used to find an optimal decision policy. However, these techniques do not scale well to large problems, since their computational cost grows fast with the number of possible states in the task. This work presents an approach to create a compact model of an MDP. The stochastic factorization developed here formalizes a simple idea: the dimension of a Markov decision process can be significantly reduced by simply redirecting its transitions to a small set of “archetypical states” which represent its dynamics well. Using this compact model, it is possible to find a decision policy within a small fraction of the time that would be required to solve the problem with the original MDP. The performance of the resulting policies depends only on the quality of the stochastic factorization: in particular, an exact factorization leads to an optimal solution with probability one. In order to demonstrate the effectiveness of the stochastic factorization in practice, the performance of the proposed algorithms is compared to that of other dynamic programming and reinforcement-learning techniques in simple benchmark tasks.
