O Que É Programação Dinâmica?

É particularmente útil em aprendizado por reforço (RL) para resolver processos de decisão de Markov (MDPs) de forma eficiente quando um modelo completo do ambiente está disponível.

Condições para Aplicação de DP

Nem todo problema pode ser resolvido com DP. Existem dois atributos principais que um problema deve possuir para que DP funcione:

• Subestrutura ótima: a solução ótima de um problema é derivada das soluções ótimas de seus subproblemas. Em MDPs, isso significa que a política ótima em qualquer estado depende das políticas ótimas dos estados seguintes. Como as decisões em um MDP são sequenciais, resolver subproblemas menores (encontrar a melhor ação para estados futuros) leva à resolução do problema geral (encontrar a melhor ação para o estado atual);
• Subproblemas sobrepostos: soluções para subproblemas são reutilizadas para resolver problemas maiores. Em MDPs, isso é evidente porque o valor de um estado é calculado repetidamente em diferentes sequências de decisão. Como os estados são frequentemente revisitados, valores previamente computados podem ser armazenados e reutilizados, reduzindo cálculos redundantes e melhorando a eficiência.

Cada nó na imagem representa uma chamada recursiva para calcular Fib(n), e a estrutura em árvore mostra como essas chamadas são divididas em subproblemas menores. Observe que subproblemas como Fib(2) e Fib(1) aparecem várias vezes, demonstrando subproblemas sobrepostos, enquanto a solução para Fib(5) é construída a partir das soluções ótimas de seus subproblemas, demonstrando subestrutura ótima. Essa redundância é o que a programação dinâmica busca eliminar, armazenando e reutilizando resultados.

Como os MDPs apresentam tanto subestrutura ótima quanto subproblemas sobrepostos, eles são adequados para soluções baseadas em programação dinâmica.

Por que usar PD em RL?

• Garantias de otimalidade: métodos de PD garantem convergência para a política ótima quando o modelo completo é conhecido;
• Eficiência para soluções gerais: com o auxílio da PD, soluções gerais podem ser obtidas de forma eficiente, significando que a política resultante será ótima para cada estado individualmente;
• Fundamento para outros métodos: conceitos de PD servem como base para outros métodos de RL, como Monte Carlo e aprendizado por diferença temporal.

No entanto, a PD não é viável para problemas em larga escala devido à sua dependência de um modelo completo e à demanda computacional, o que leva aos desafios discutidos a seguir.

Desafios e Limitações da Programação Dinâmica

Embora a PD forneça uma estrutura elegante para resolver problemas de RL, ela apresenta desafios significativos que limitam sua aplicabilidade em cenários do mundo real:

• Complexidade computacional: Métodos de PD exigem cálculos para cada estado em um ambiente. À medida que o espaço de estados cresce, o número de cálculos necessários aumenta significativamente, tornando a PD impraticável para problemas complexos;
• Necessidade de um modelo conhecido: A PD assume que as probabilidades de transição e recompensas do ambiente são conhecidas previamente. No entanto, em muitas aplicações reais de RL, essas informações não estão disponíveis, tornando abordagens sem modelo mais práticas.