Dynamic Programming in AI & Artificial Intelligence

The fundamental insight of Dynamic Programming (DP) is that the value of a state can be defined recursively. The Bellman Equation tells us that the value of being in state $s$ is the immediate reward we expect, plus the discounted value of where we might end up next. By turning this equation into an 'Update Rule', we can iteratively refine our estimates of how 'good' every position in our world truly is.

There are two primary ways to find the optimal solution: Policy Iteration and Value Iteration. Policy Iteration alternates between evaluating the current strategy and improving it. Value Iteration is faster—it effectively combines these steps by directly updating the state values to the maximum possible expected return at each step. Both are guaranteed to converge to the optimal solution for finite MDPs with known transitions.

While DP is mathematically perfect, it suffers from the Curse of Dimensionality. Because it requires a 'Sweep' over every single state in the environment, it becomes impossibly slow for complex worlds like Chess, Go, or robotics. This is why we move toward Approximation and Model-Free methods in later stages—but the core principles of DP remain the target they all aim to hit.

When you have a perfect map of the world, you don't need to explore—you can calculate. Dynamic Programming (DP) is the method for solving MDPs when the transition rules are known.

DP relies on two core processes: Policy Evaluation (calculating the value of a strategy) and Policy Improvement (making the strategy better based on those values).

The Bellman Expectation Equation is the engine. It breaks down the value of a state into the immediate reward plus the discounted value of the next state.

Checkpoint: What is the requirement for using Dynamic Programming to solve a Reinforcement Learning problem?

• →A massive amount of historical data
• →A complete and accurate model of the environment (Transitions and Rewards)

We use 'Value Iteration' to sweep through all states repeatedly until the values stabilize. This gives us the 'Optimal Value Function', from which the optimal policy is easily found.

DP is computationally heavy for large worlds, but it provides the 'Gold Standard' mathematical solution that all other RL algorithms try to approximate.

Checkpoint: In Policy Improvement, how do we choose the new action for a state?

• →Random selection
• →Choosing the action that maximizes the expected return (Greedy approach)

Dynamic Programming mastered! You've learned to calculate optimal paths. Ready to learn how to do this WITHOUT a map using Monte Carlo methods?

Run a Real Bellman Update. Finish one Bellman backup step, combining the immediate reward with the discounted value of the next state.