A 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.1 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?2 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. Our modeling above is an instance of something called a state machine or automata if you’re into Greek words. There are 4 states in which the character might be and at each one there is an available set of actions to take that transitions that state. More abstractly, an automaton is a system that can be in one of many states s \in \mathcal{S} and at each state, you can choose among a set of actions a \in \mathcal{A}(s). Whenever you take an action, the system changes to a new state according to a transition function T : (s : \mathcal{S}) \times \mathcal{A}(s) \to \mathcal{S}. Unfortunately life is not known for its free lunches and, in general, whenever one takes action a at state s, it is necessary to pay a certain cost, properly modeled as another function c : (s : \mathcal{S}) \times \mathcal{A}(s) \to \mathbb{R}. Depending on the context this can be, for example, a real monetary cost (in economic contexts), some total distance or elapsed time (for planning) or even a negative cost representing a reward. The Dynamics of Decision-Making Iterating the transition T establishes a dynamics for our system: by starting at an initial state s_0 and taking a sequence of actions \{a_t\}, we generate a trajectory over the state space. s_{t+1} = T(s_t, a_t). When viewed in this light, our state machines are called controllable dynamical systems or decision processes, which are yet additional cool names for you to memorize. One can argue that a state encapsulates all you must know about your system in order to choose an action, no matter the previous history nor time step. Indeed, if any other thing affects your choice, you can, without loss of generality, model the process as a larger automaton where the state also carries the additional information. Thus, controlling a dynamic system amounts to selecting a valid action for each state, that is, a function \pi : (s : \mathcal{S}) \to \mathcal{A}(s). In the literature this is called a policy, in analogy to a government taking actions to control the state of the nation. Starting at state s_0 and following a policy \pi produces a deterministic dynamical system without the need for choosing a control: s_{t+1} = T(s_t, \pi(s_t)). This dynamics, in counterpart, yields a cost c(s_t, \pi(s_t)) for each time step. We could define the total cost for \pi as the sum of those costs, but there is an additional detail to notice. Suppose that, for any reason, money is short and you had to take a loan in order to pay your bills. In those struggling conditions, would you prefer to pay the money back today or next year? Sometimes there are factors such as inflation or interests making future costs have a real value that is different from its nominal value. This prompts us to introduce a problem dependent discount factor \gamma \in [0, 1] representing how much the cost depreciates over time. The total cost of following a certain policy \pi is the cumulative sum of all properly discounted costs we generate by following it. We define the value function v^\pi : \mathcal{S}\to \mathbb{R} associated with \pi as the total cost of starting at a given state: \begin{array}{rl} v^\pi(s) = & c(s_0, \pi(s_0)) + \gamma c(s_1, \pi(s_1)) + \gamma^2 c(s_2, \pi(s_2)) + \ldots \\ \textrm{where} & s_0 = s, \\ & s_{t+1} = T(s_t, \pi(s_t)), \\ \end{array} Besides from its practical interpretation, the discount factor \gamma also plays a significant role from the analytical point of view. If |\gamma| < 1 and the costs are uniformly bounded (which is the case for a finite action space, for example) we can guarantee that the series defining v^\pi converges for any choice of actions and initial state. That is, suppose there exists M > 0 such that \forall s \in \mathcal{S}, a \in \mathcal{A}(s),\, |c(s, a)| \le M. This bounds the total cost by a geometric series that cannot blow up, \sum\limits_{t=0}^\infty \gamma^{t}|c(s_t, a_t)| \le \sum\limits_{t=0}^\infty \gamma^{t} M \le \frac{M}{1 - \gamma}, Thus guaranteeing that the value function is well-defined. Optimal Decisions Having multiple possible courses of action prompts us to ask which one is the best. When programming a robot to escape a labyrinth, you want it to take the least amount of time; When controlling a spaceship towards the moon, it is important to guarantee that it will use the least amount of fuel; When brawling at a bar, you want to knock out your foe while sustaining the least injuries possible. Most of all, the best policy is the one with the least cost taking all time into account — both the present and its future consequences. For example, sometimes a policy that has a higher cost for the first state is overall better because it puts us into a more favorable state. Thus, our problem can be naturally formulated as searching for optimal policies: Starting at state s, find a policy \pi producing the least total cost over time. Or equivalently in math language: \begin{array}{rl} \min\limits_\pi v^\pi(s) = \min\limits_{a_t} & \sum\limits_{t=0}^\infty \gamma^{t}c(s_t, a_t) \\ \textrm{s.t.} & s_0 = s, \\ & s_{t+1} = T(s_t, a_t), \\ & a_t \in \mathcal{A}(s_t). \end{array} Right now, this may seem like a big and scary optimization problem but in fact it contains a lot of structure we’re able to exploit. That is the subject of the next section. But, before we continue, let’s go over a little tangent on how to formulate some classical problems in this decision-making framework. Example: Shortest Path in a Graph Suppose you are at your hometown and just received a message from a friend telling you that there are singing llamas in Cuzco, Peru, right now. This makes you at the same time incredulous and curious, so you just pick your favorite bike and get on the road towards Cuzco. Unfortunately there are no direct bikeways connecting your home to Cuzco, meaning that you will have to find a route going through other cities. Also, there is a risk that the llamas will stop to sing at any time and just go back to their usual behavior of eating grass throughout the mountains. This prompts you to decide to take the shortest possible path to Cuzco. The above description is an instance of finding the shortest path in a graph. In it, we represent each city by a graph node and direct routes between two cities as a weighted edge where the weight is the distance. Going from home to Cuzco amounts to finding the path between those two nodes with the smallest total distance. The translation from this graph description to a decision process is quite straightforward. States: nodes in the graph. Actions at state s: edges going from s to another node. Transition: the opposite node on the same edge. That is, given an edge s \to s', T(s, s \to s') = s'. Costs: c(s, a) is the weight of edge a — the time taken traveling through that edge. Finding the