É especialmente ú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 essenciais 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 ao armazenar e reutilizar resultados.

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

Por que usar DP em RL?

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

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

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

Embora a Programação Dinâmica (DP) forneça uma estrutura elegante para resolver problemas de Aprendizado por Reforço (RL), ela apresenta desafios significativos que limitam sua aplicabilidade em cenários do mundo real:

• Complexidade computacional: Métodos de DP exigem cálculos para cada estado individual em um ambiente. À medida que o espaço de estados cresce, o número de cálculos necessários aumenta significativamente, tornando a DP impraticável para problemas complexos;
• Necessidade de um modelo conhecido: A DP 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.