RL 3: Bellman Equations and Markov Decision Processes (1950s–1960s)

In 1950s and 1960s, mathematician Richard Bellman revolutionized the field of decision making through his invention of Dynamic Programming. This concept stemmed from his work at RAND, a US think tank, where he was tasked with solving specific problems that involved making a choice, leading to a change in the world, and then making another decision based on the new circumstances. Bellman called this field of study Dynamic Programming, a term that has since become one of the most important in computer science.

The problem he tackled was framed on a grid, starting from one corner and aiming to reach a goal while collecting as much reward as possible. Each step cost a little energy, and some cells were detrimental. The obvious approach, listing all possible paths and choosing the best one, becomes unfeasible as grid size increases due to the curse of dimensionality.

Bellman's core insight, known as the Principle of Optimality, states that an optimal policy has the property that whatever the initial state and decision, the remaining decisions must form an optimal policy with regard to the new state resulting from the initial decision. In simpler terms, if the best route from point A to C goes through point B, then the B-to-C part must be the best route from B to C. This principle allows for solving each sub-problem only once, as the best way from B onward can be reused for routes passing through B, avoiding recomputation.

This method, called Dynamic Programming, involves solving a giant sequential problem from the end backward and caching the answers. The backwards approach is counterintuitive but forms the foundation of modern Reinforcement Learning (RL) agents.