5.3 Dynamic Programming

Dynamic Programming refers to a collection of general methods developed to solve sequential, or multi-stage, decision problems.¹⁰ It is an extremely versatile tool with applications in fields such as finance, supply chain management and airline scheduling. Although theoretically simple, mastering dynamic programming algorithms requires extensive mathematical prerequisites and rigorous logic. As a result, it is often perceived to be one of the most difficult graduate level courses.

Fortunately, the dynamic programming problems you are likely to encounter in interviews—although you often may not recognize them as such—are rudimentary problems. So in this section we will focus on the basic logic used in dynamic programming and apply it to several interview problems. Hopefully the solutions to these examples will convey the gist and the power of dynamic programming.

A discrete-time dynamic programming model includes two inherent components:

1. The underlying discrete-time dynamic system

A dynamic programming problem can always be divided into stages with a decision required at each stage. Each stage has a number of states associated with it. The decision at one stage transforms the current state into a state in the next stage (at some stages and states, the decision may be trivial if there is only one choice).

Assume that the problem has $N+1$ stages (time periods). Following the convention, we label these stages as $0,1,\cdots,N-1,N$. At any stage $k,\ 0\le k\le N-1$, the state transition can be expressed as $x_{k+1}=f(x_k,u_k,w_k)$, where $x_k$ is the state of system at stage $k$;¹¹ $u_k$ is the decision selected at stage $k$; $w_k$ is a random parameter (also called disturbance).

Basically the state of next stage $x_{k+1}$ is determined as a function of the current state $x_k$, current decision $u_k$ (the choice we make at stage $k$ from the available options) and the random variable $w_k$ (the probability distribution of $w_k$ often depends on $x_k$ and $u_k$).

2. A cost (or profit) function that is additive over time.

Except for the last stage $(N)$, which has a cost/profit $g_N(x_N)$ depending only on $x_N$, the costs at all other stages $g_k(x_k,u_k,w_k)$ can depend on $x_k$, $u_k$, and $w_k$. So the total cost/profit is $\displaystyle g_N(x_N)+\sum_{k=i}^{N-1}g_k(x_k,u_k,w_k)\}$.

The goal of optimization is to select strategies/policies for the decision sequences $\pi^*=\{u_0^*,\cdots,u_{N-1}^*\}$ that minimize expected cost (or maximize expected profit):

Dynamic programming (DP) algorithm

The dynamic programming algorithm relies on an idea called the Principle of Optimality: If $\pi^*=\{u_0^*,\cdots,u_{N-1}^*\}$ is the optimal policy for the original dynamic programming problem, then the tail policy $\pi_i^*=\{u_i^*,\cdots,u_{N-1}^*\}$ must be optimal for the tail subproblem $\displaystyle E\left\{g_N(x_N)+\sum_{k=i}^{N-1}g_k(x_k,u_k,w_k)\right\}$.

DP algorithm: To solve the basic problem $\displaystyle J_{\pi^*}(x_0)=\min_\pi E\left\{g_N(x_N)+\sum_{k=0}^{N-1}g_k(x_k,u_k,w_k)\right\}$, start with $J_N(x_N)=g_N(x_N)$, and go backwards minimizing cost-to-go function $J_k(x_k)$:

Then the $J_0(x_0)$ generated from this algorithm is the expected optimal cost.

Although the algorithm looks complicated, the intuition is straightforward. For dynamic programming problems, we should start with optimal policy for every possible state of the final stage (which has the highest amount of information and least amount of uncertainty) first and then work backward towards earlier stages by applying the tail policies and cost-to-go functions until you reach the initial stage.

Now let’s use several examples to show how the DP algorithm is applied.

Dice game

You can roll a 6-side dice up to 3 times. After the first or the second roll, if you get a number $x$, you can decide either to get $x$ dollars or to choose to continue rolling. But once you decide to continue, you forgo the number you just rolled. If you get to the third roll, you’ll just get $x$ dollars if the third number is $x$ and the game stops. What is the game worth and what is your strategy?

Solution: This is a simple dynamic programming strategy game. As all dynamic programming questions, the key is to start with the final stage and work backwards. For this question, it is the stage where you have forgone the first two rolls. It becomes a simple dice game with one roll. Face values 1, 2, 3, 4, 5, and 6 each have a 1/6 probability and your expected payoff is $3.5.

Now let’s go back one step. Imagine that you are at the point after the second roll, for which you can choose either to have a third roll with an expected payoff of $3.5 or keep the current face value. Surely you will keep the face value if it is larger than 3.5; in other words, when you get 4, 5 or 6, you stop rolling. When you get 1, 2 or 3, you keep rolling. So your expected payoff before the second roll is $3/6\times3.5+1/6\times(4+5+6)=\$4.25$.

Now let’s go back one step further. Imagine that you are at the point after the first roll, for which you can choose either to have a second roll with expected payoff $4.25 (when face value is 1, 2, 3 or 4) or keep the current face value. Surely you will keep the face value if it is larger than 4.25; In other words, when you get 5 or 6, you stop rolling. So your expected payoff before the first roll is $4/6\times4.25+1/6\times(5+6)=\$14/3$.

This backward approach—called tail policy in dynamic programming—gives us the strategy and also the expected value of the game at the initial stage, $$14/3$.

World series

The Boston Red Sox and the Colorado Rockies are playing in the World Series finals. In case you are not familiar with the World Series, there are a maximum of 7 games and the first team that wins 4 games claims the championship. You have $100 dollars to place a double-or-nothing bet on the Red Sox.

Unfortunately, you can only bet on each individual game, not the series as a whole. How much should you bet on each game so that if the Red Sox wins the whole series, you win exactly $100, and if Red Sox loses, you lose exactly $100?

Solution: Let $(i,j)$ represents the state that the Red Sox has won $i$ games and the Rockies has won $j$ games, and let $f(i,j)$ be our net payoff, which can be negative when we lose money, at state $(i,j)$. From the rules of the game, we know that there may be between 4 and 7 games in total. We need to decide on a strategy so that whenever the 124 series is over, our final net payoff is either +100—when Red Sox wins the championship—or -100—when Red Sox loses. In other words, the state space of the final stage includes $\{(4,0),(4,1),(4,2),(4,3)\}$ with payoff $f(i,j)=100$ and $\{(0,4),(1,4),(2,4),(3,4)\}$ with payoff $f(i,j)=-100$. As all dynamic programming questions, the key is to start with the final stage and work backwards—even though in this case the number of stages is not fixed. For each state $(i,j)$, if we bet $$y$ on the Red Sox for the next game, we will have $(f(i,j)+y)$ if the Red Sox wins and the state goes to $(i+1,j)$, or $(f(i,j)-y)$ if the Red Sox loses and the state goes to $(i,j+1)$. So clearly we have

For example, we have $\displaystyle f(3,3)=\frac{f(4,3)+f(3,4)}{2}=\frac{100-100}{2}=0$. Let’s set up a table with the columns representing $i$ and the rows representing $j$. Now we have all the information to fill in $f(4,0),$ $f(4,1),$ $f(4,3),$ $f(4,2),$ $f(0,4),$ $f(1,4),$ $f(2,4),$ $f(3,4)$, as well as $f(3,3)$. Similarly we can also fill in all $f(i,j)$ for the states where $i=3$ or $j=3$ as shown in Figure 5.7. Going further backward, we can fill in the net payoffs at every possible state. Using equation $y=(f(i+1,j)-f(i,j+1))/2$, we can also calculate the bet we need to place at each state, which is essentially our strategy.

If you are not accustomed to the table format, Figure 5.8 redraws it as a binomial tree, a format you should be familiar with. If you consider that the boundary conditions are $f(4,0),$ $f(4,1),$ $f(4,3),$ $f(4,2),$ $f(0,4),$ $f(1,4),$ $f(2,4)$, and $f(3,4)$, the underlying asset either increases by 1 or decrease by 1 after each step, and there is no interest, then the problem becomes a simple binomial tree problem and the bet we place each time is the delta in dynamic hedging. In fact, both European options and American options can be solved numerically using dynamic programming approaches.

Dynamic dice game

A casino comes up with a fancy dice game. It allows you to roll a dice as many times as you want unless a 6 appears. After each roll, if 1 appears, you will win $1; if 2 appears, you will win $2; …; if 5 appears, you win $5; but if 6 appears all the moneys you have won in the game is lost and the game stops. After each roll, if the dice number is 1-5, you can decide whether to keep the money or keep on rolling. How much are you willing to pay to play the game (if you are risk neutral)?¹²

Solution: Assuming that we have accumulated $n$ dollars, the decision to have another roll or not depends on the expected profit versus expected loss. If we decide to have an extra roll, our expected payoff will become

We have another roll if the expected payoff $\frac56n+2.5>n$, which means that we should keep rolling if the money is no more than $14. Considering that we will stop rolling when $n\ge15$, the maximum payoff of the game is $19 (the dice rolls a 5 after reaching the state $n=14$). We then have the following: $f(19)=19,$ $f(18)=18,$ $f(17)=17,$ $f(16)=16,$ and $f(15)=15$. When $n\le14$, we will keep on rolling, so $\displaystyle E[f(n)\mid n\le14]=\frac16\sum_{i=1}^5E[f(n+i)]$. Using this equation, we can calculate the value for $E[f(n)]$ recursively for all $n=14,13,\cdots,0$. The results are summarized in Table 5.2. Since $E[f(0)]=6.15$, we are willing to pay at most $6.15 for the game.

Dynamic card game

A casino offers yet another card game with the standard 52 cards (26 red, 26 black). The cards are thoroughly shuffled and the dealer draws cards one by one. (Drawn cards are not returned to the deck.) You can ask the dealer to stop at any time you like. For each red card drawn, you win $1; for each black card drawn, you lose $1. What is the optimal stopping rule in terms of maximizing expected payoff and how much are you willing to pay for this game?

Solution: It is another problem perceived to be difficult by many interviewees. Yet it is a simple dynamic programming problem. Let $(b,r)$ represent the number of black and red cards left in the deck, respectively. By symmetry, we have

red cards drawn − black cards drawn = black cards left − red cards left = $b-r$

At each $(b,r)$, we face the decision whether to stop or keep on playing. If we ask the dealer to stop at $(b,r)$, the payoff is $b-r$. If we keep on going, there is $\frac{b}{b+r}$ probability that the next card will be black—in which case the state changes to $(b-1,r)$—and $\frac{r}{b+r}$ probability that the next card will be red—in which case the state changes to $(b,r-1)$. We will stop if and only if the expected payoff of drawing more cards is less than $b-r$. That also gives us the system equation:

As shown in Figure 5.9 (next page), using the boundary conditions $f(0,r)=0,\ f(b,0)=b,\ \forall b,r=0,1,\cdots,26$, and the system equation for $E[f(b,r)]$, we can recursively calculate $E[f(b,r)]$ for all pairs of $b$ and $r$.

The expected payoff at the beginning of the game is $E[f(26,26)]=\$2.62$.