GoKawiilA Tale of Dynamic Programming
What if I told you that some of the most used algorithms to find the shortest path in a graph, calculate gradients while training a neural network, and parse context-free grammars are essentially implementations of the same principle? It is called dynamic programming and is one of those instances in mathematics where a simple principle unfolds into profound conclusions ranging over many fields. In fact, we can, already in this first paragraph, summarize the idea using Richard Bellman’s (Dynamic Programming’s creator) own words:
An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.
I have to admit that despite encountering dynamic programming in different contexts, it took me a while to finally get the “click” that they were actually the same thing. When learning algorithms and data structures, it was a memoization-based technique where you could speed up some algorithms by first solving the easier parts and storing the solution for later use. Then, at work, I mostly deal with solving a lot of linear programs for long-term scheduling problems. The main algorithm we use, called Stochastic Dual Dynamic Programming, at first didn’t seem so much like the programming technique from the algorithms class. Finally, one of the main methods for model-based reinforcement learning is again called dynamic programming, and it also didn’t seem so much like the other instances.
So, what’s happening here? Did everybody choose to call their algorithms dynamic programming just because it’s a cool name? Well, in fact there are some principles that apply to all of those instances, from planning a rocket’s trajectory to TeX’s word-wrapping. And the list goes on and on.
I want to invite you to a journey through many realms of mathematics. We will range from automata to optimal control, passing through Markov chains, dynamical systems, linear programming and even metric spaces. Take your seat and enjoy the ride!
On Decision-Making and State Machines
Before delving into dynamic programming per se, we first have to establish a few concepts. After all, it’s always best to know which problems you intend to solve before learning a method to solve them, right?
As a matter of motivation, let’s start with something I am really fond of: old school plataformer games. In our hypothetical game which is definitely not about some Italian plumber, the character stands idle doing nothing by default. But with the press of a button in the controller, the player may command the character to do a few things: shoot, jump, or walk. And, of course, each of these actions activate the respective animation on the screen. In the best Resident Evil style, this game only allows a character to shoot while idle and forces you to first be idle after a jump before doing any other action. Think of that as the time it takes to restore one’s balance after falling. This description may seem overly complicated on text, but fortunately the nice folks in the Comp Sci department already invented diagrams that show these transitions nicely.
Browser lacks SVG support.
... continue reading