Es especialmente útil en el aprendizaje por refuerzo (RL) para resolver procesos de decisión de Markov (MDP) de manera eficiente cuando se dispone de un modelo completo del entorno.

Condiciones para aplicar DP

No todos los problemas pueden resolverse con DP. Existen dos atributos clave que un problema debe tener para que DP funcione:

• Subestructura óptima: la solución óptima de un problema se deriva de las soluciones óptimas de sus subproblemas. En los MDP, esto significa que la política óptima en cualquier estado depende de las políticas óptimas de los estados siguientes. Dado que las decisiones en un MDP son secuenciales, resolver subproblemas más pequeños (encontrar la mejor acción para estados futuros) conduce a resolver el problema general (encontrar la mejor acción para el estado actual);
• Subproblemas superpuestos: las soluciones a los subproblemas se reutilizan para resolver problemas más grandes. En los MDP, esto es evidente porque el valor de un estado se calcula repetidamente a lo largo de diferentes secuencias de decisiones. Como los estados suelen ser revisitados, los valores previamente calculados pueden almacenarse y reutilizarse, reduciendo cálculos redundantes y mejorando la eficiencia.

Cada nodo en la imagen representa una llamada recursiva para calcular Fib(n), y la estructura del árbol muestra cómo estas llamadas se descomponen en subproblemas más pequeños. Observa que subproblemas como Fib(2) y Fib(1) aparecen varias veces, lo que demuestra subproblemas superpuestos, mientras que la solución de Fib(5) se construye a partir de las soluciones óptimas de sus subproblemas, demostrando subestructura óptima. Esta redundancia es lo que la programación dinámica busca eliminar almacenando y reutilizando resultados.

Dado que los MDP presentan tanto subestructura óptima como subproblemas superpuestos, son adecuados para soluciones basadas en DP.

¿Por qué usar DP en RL?

• Garantías de optimalidad: los métodos de DP garantizan la convergencia hacia la política óptima cuando se conoce el modelo completo;
• Eficiencia para soluciones generales: con la ayuda de DP, se pueden obtener soluciones generales de manera eficiente, lo que significa que la política resultante será óptima para cada estado individual;
• Fundamento para otros métodos: los conceptos de DP sirven como base para otros métodos de RL, como Monte Carlo y aprendizaje por diferencia temporal.

Sin embargo, DP no es factible para problemas a gran escala debido a su dependencia de un modelo completo y a las demandas computacionales, lo que conduce a los desafíos que se discuten a continuación.

Desafíos y limitaciones de la programación dinámica

Aunque la Programación Dinámica (DP) proporciona un marco elegante para resolver problemas de Aprendizaje por Refuerzo (RL), presenta desafíos significativos que limitan su aplicabilidad en escenarios del mundo real:

• Complejidad computacional: Los métodos de DP requieren cálculos para cada estado individual en un entorno. A medida que el espacio de estados crece, el número de cálculos necesarios aumenta significativamente, haciendo que DP sea poco práctico para problemas complejos;
• Necesidad de un modelo conocido: DP asume que las probabilidades de transición y las recompensas del entorno se conocen de antemano. Sin embargo, en muchas aplicaciones reales de RL, esta información no está disponible, lo que hace que los enfoques sin modelo sean más prácticos.