A Tale of Dynamic Programming | Iago Leal de Freitas
What if I told you that some of the most used<br>algorithms to find the shortest path in a graph,<br>calculate gradients while training a neural network, and<br>parse context-free grammars are essentially<br>implementations of the same principle? It is called<br>dynamic programming and is one of those<br>instances in mathematics where a simple principle<br>unfolds into profound conclusions ranging over many<br>fields. In fact, we can, already in this first<br>paragraph, summarize the idea using Richard Bellman’s<br>(Dynamic Programming’s creator) own words:
An optimal policy has the property that whatever the<br>initial state and initial decision are, the remaining<br>decisions must constitute an optimal policy with regard<br>to the state resulting from the first decision.
I have to admit that despite encountering dynamic<br>programming in different contexts, it took me a while to<br>finally get the “click” that they were actually the same<br>thing. When learning algorithms and data structures, it<br>was a memoization-based technique where you could speed<br>up some algorithms by first solving the easier parts and<br>storing the solution for later use. Then, at work, I<br>mostly deal with solving a lot of linear programs for<br>long-term scheduling problems.1 The main algorithm<br>we use, called Stochastic Dual Dynamic<br>Programming, at first didn’t seem so much like the<br>programming technique from the algorithms class.<br>Finally, one of the main methods for model-based<br>reinforcement learning is again called dynamic<br>programming, and it also didn’t seem so much like the<br>other instances.
So, what’s happening here? Did everybody choose to<br>call their algorithms dynamic programming just because<br>it’s a cool name?2 Well, in<br>fact there are some principles that apply to all of<br>those instances, from planning a rocket’s trajectory to<br>TeX’s word-wrapping. And the list<br>goes on and on.
I want to invite you to a journey through many realms<br>of mathematics. We will range from automata to optimal<br>control, passing through Markov chains, dynamical<br>systems, linear programming and even metric spaces. Take<br>your seat and enjoy the ride!
On<br>Decision-Making and State Machines
Before delving into dynamic programming per se, we<br>first have to establish a few concepts. After all, it’s<br>always best to know which problems you intend to solve<br>before learning a method to solve them, right?
As a matter of motivation, let’s start with something<br>I am really fond of: old school plataformer games. In<br>our hypothetical game which is definitely not about some<br>Italian plumber, the character stands idle doing nothing<br>by default. But with the press of a button in the<br>controller, the player may command the character to do a<br>few things: shoot, jump, or walk. And, of course, each<br>of these actions activate the respective animation on<br>the screen. In the best Resident Evil style, this game<br>only allows a character to shoot while idle and forces<br>you to first be idle after a jump before doing any other<br>action. Think of that as the time it takes to restore<br>one’s balance after falling. This description may seem<br>overly complicated on text, but fortunately the nice<br>folks in the Comp Sci department already invented<br>diagrams that show these transitions nicely.
Browser lacks SVG support.
Our modeling above is an instance of something called<br>a state machine or automata if you’re<br>into Greek words. There are 4 states in which the<br>character might be and at each one there is an available<br>set of actions to take that transitions that state. More<br>abstractly, an automaton is a system that can be in one<br>of many states s \in<br>\mathcal{S} and at each state, you can choose<br>among a set of actions a \in \mathcal{A}(s).<br>Whenever you take an action, the system changes to a new<br>state according to a transition function
T : (s : \mathcal{S})<br>\times \mathcal{A}(s) \to \mathcal{S}.
Unfortunately life is not known for its free lunches<br>and, in general, whenever one takes action a at state s, it is necessary to pay a<br>certain cost, properly modeled as another<br>function
c : (s : \mathcal{S})<br>\times \mathcal{A}(s) \to \mathbb{R}.
Depending on the context this can be, for example, a<br>real monetary cost (in economic contexts), some total<br>distance or elapsed time (for planning) or even a<br>negative cost representing a reward.
The Dynamics of<br>Decision-Making
Iterating the transition T establishes a dynamics for<br>our system: by starting at an initial state s_0 and taking a sequence of<br>actions \{a_t\}, we<br>generate a trajectory over the state space.
s_{t+1} = T(s_t, a_t).
When viewed in this light, our state machines are<br>called controllable dynamical systems or<br>decision processes, which are yet additional<br>cool names for you to memorize.
One can argue that a state encapsulates all you must<br>know about your system in order to choose an action, no<br>matter the previous history nor time step. Indeed, if<br>any other thing affects your choice, you can, without<br>loss of generality, model the process as a...