What is Dynamic Programming?

Dynamic programming (DP) is a fundamental approach to solving mathematical optimization problems. It is particularly useful in reinforcement learning (RL) for solving Markov decision processes (MDPs) efficiently when a complete model of the environment is available.

In general, DP methods help solve complex problems by breaking down big problems into smaller subproblems and solving them recursively. Instead of solving the same problem repeatedly, DP leverages previously computed solutions to speed up the process.

Conditions for Applying DP

Not every problem can be solved with DP. There are two key attributes that a problem must have in order for DP to work:

• Optimal substructure: the optimal solution to a problem is derived from the optimal solutions of its subproblems. In MDPs, this means that the optimal policy at any state depends on the optimal policies of the following states. Because decisions in an MDP are sequential, solving smaller subproblems (finding the best action for future states) leads to solving the overall problem (finding the best action for the current state);
• Overlapping subproblems: solutions to subproblems are reused to solve larger problems. In MDPs, this is evident because the value of a state is repeatedly calculated across different decision sequences. Since states are often revisited, previously computed values can be stored and reused, reducing redundant computations and improving efficiency.

Since MDPs exhibit both optimal substructure and overlapping subproblems, they are well-suited for DP-based solutions.

Why Use DP in RL?

• Optimality guarantees: DP methods are guaranteed to converge to the optimal policy when the full model is known;
• Efficiency for general solutions: with the help of DP, general solutions can be efficiently obtained, meaning that the resulting policy will be optimal for every single state;
• Foundational for other methods: concepts from DP serve as the basis for other RL methods, such as Monte Carlo and temporal difference learning.

However, DP is not feasible for large-scale problems due to its reliance on a full model and computational demands, which leads to the challenges discussed next.

Challenges and Limitations of Dynamic Programming

While DP provides an elegant framework for solving RL problems, it comes with significant challenges that limit its applicability in real-world scenarios:

• Computational complexity: DP methods require computations for every single state in an environment. As the state space grows, the number of required computations increases significantly, making DP impractical for complex problems;
• Need for a known model: DP assumes that the environment's transition probabilities and rewards are known in advance. However, in many real-world RL applications, this information is unavailable, making model-free approaches more practical.

Summary

DP approach provides a structured way to solve MDPs when the environment's dynamics are fully known. It guarantees optimal solutions and serves as the foundation for more scalable RL methods. However, its reliance on a complete model and computational inefficiency make it impractical for large-scale problems.