1 Prelude: Examples of Dynamic Programs

Dynamic programming is a recursive technique for solving optimization problems. While initially developed for intertemporal problems (inventory management, investment planning, optimal savings and consumption, etc.), it has since been applied to various atemporal problems, ranging from genome sequencing and matrix multiplication to the structure of production chains. Creators of machine learning and artificial intelligence routinely use dynamic programming.

The sheer breadth of applications currently being tackled with dynamic programming is a challenge for presenting a modern theory. As well as the vast range of concrete problems faced in applied settings, researchers are adding features to their models that require extensions of the foundations of dynamic programming. Such new features include time-varying discount rates, nonlinear discounting, risk-sensitive control, ambiguity aversion, nonlinear time aggregation, and so on. Researchers added these features in their quests to create new models capable of coming closer to data sets of interest.

To set the scene, we begin with some problems that can be handled using classic methods. Then we discuss extensions and transformations that require more sophisticated theoretical foundations. Since our purpose here is to set the stage for the abstract theory that is the main focus of this Volume, our presentation here is mathematically informal at many points. Results stated in this chapter are special cases of the abstract theory, which begins in Chapter 2.

1.1A Firm Problem¶

This section uses a firm valuation and control problem to introduce core dynamic programming concepts. We begin with traditional methods, showing how recursive representations lead to the Bellman equation and optimal policies. We then discuss extensions involving unbounded rewards, time-varying discount rates, and risk-sensitive preferences.

1.1.1Models of a Firm¶

We first consider firm valuation under a Markov profit process, deriving a recursive representation for expected present value. Next, by giving the manager an option to sell the firm at a time of their choosing, we add a control. A Bellman type of optimality is then stated and proved. This material establishes a template for dynamic programs that recur throughout this chapter.

1.1.1.1Valuation¶

A firm generates a random flow of profits $(\pi_t)_{t \geq 0} = \pi_0, \pi_1, \pi_2, \ldots$. At time $t$, a manager wants to calculate the present value of the profit process. Current profits $\pi_t$ are known but future values $\pi_{t+1}, \pi_{t+2}, \ldots$ are not. The manager knows the distribution of the process $(\pi_t)_{t \geq 0}$. Consequently the manager can compute the expected present value, namely

Here $\beta$ is a discount factor, often reparameterized as $\beta = 1/(1+r)$ when $r$ is a discount rate. Thus, $\beta^m \pi_{t+m}$ is time $t+m$ profits discounted to the present date $t$. The symbol $\EE_t$ denotes mathematical expectation conditional on time $t$ information.

We can switch to a recursive representation of the sequence of valuations $(V_t)_{t \geq 0}$ by first writing

and then applying the law of iterated expectations $\EE_t = \EE_t \EE_{t+1}$. This leads to

This expression will be important for us because the theory of dynamic programming is built around recursive relationships. Later we will see many variations of (1.3).

To make further progress in computing $(V_t)_{t \geq 0}$, let’s assume that $\pi_t = \pi(X_t)$, where $(X_t)_{t \geq 0}$ is a discrete time Markov process taking values in a measurable space $(\Xsf, \bB)$. We assume that $(X_t)_{t \geq 0}$ is driven by a stochastic kernel $P$ (see Section A.5.4.1), so that $P(X_t, B)$ is the probability that $X_{t+1} \in B \in \bB$ given current state $X_t$. The function $\pi$ is assumed to be in $b\Xsf$, the set of bounded, $\bB$-measurable functions from $\Xsf$ to $\RR$. We understand $X_t$ as representing the “state of the world”, including all factors affecting firm profits. Figure 1.1 shows multiple realizations of the profit process $(\pi_t)_{t \geq 0}$ in the case where $\Xsf = \RR$, $\bB$ is the Borel sets, $\pi(x) = \exp(x)$, and $(X_t)$ is a discretization of an AR(1) process with $\rho = 0.9$ and $\nu = 0.2$.

Under the Markov profits assumption, $V_t$ will depend on the current state $X_t$, since knowing the state helps predict future profits. At the same time, the Markov assumption means that earlier values $X_0, \ldots, X_{t-1}$ will not aid prediction once $X_t$ is known. This leads us to conjecture that $V_t = v(X_t)$ for some fixed function $v \colon \Xsf \to \RR$. Inserting this conjecture into (1.3) and evaluating at $X_t = x$ yields

Defining $(Pv)(x) \coloneq \int v(x') P(x, \diff x')$, which is consistent with the operator-theoretic notation in Section A.5.4, we can rewrite (1.4) as $v = \pi + \beta P v$. Using the fact that $\pi \in b\Xsf$, and that the spectral radius of $\beta P$ is $\beta$ (Lemma A.5.30), this equation has a unique solution for $v$ in $b\Xsf$ whenever $\beta < 1$. The Neumann series lemma (Theorem A.4.10) tells us that the solution has the form

Figure 1.2 plots $v = (I - \beta P)^{-1} \pi$ over the state space $\Xsf$ for several choices of the discount factor $\beta$. The environment is the same as the one underlying Figure 1.1. As $\beta$ increases, the firm places greater weight on future profits, resulting in higher valuations across all states.

Notice how the difficult problem of computing a stochastic process $(V_t)_{t \geq 0}$ has been converted into the much easier problem of calculating $v = (I - \beta P)^{-1} \pi$.

1.1.1.2Control¶

So far our manager has had no choice to make. Let’s now give the manager the option to sell the firm to an outside buyer at the start of each period (before receiving current profits) for the fixed price $s$. We will describe the manager’s decision with a binary policy function $\sigma$ that selects between selling the firm in the current period, after observing the current state $x$, and not selling --- in which case the manager again faces the option to sell the firm at the beginning of the next period. The same policy $\sigma$ is applied in every period, with $\sigma(x) \in \{0,1\}$ being the current decision. Modifying (1.4) appropriately to a $\sigma$-dependent value function, we obtain the Bellman equation

where $v_\sigma(x)$ is the total value of the firm under the policy $\sigma$, conditional on state $x$. If $\sigma(x) = 1$, then the manager sells at payoff $s$ and the process ends, so $s$ is the total value received. Otherwise $\sigma(x) = 0$, indicating no sale, profit $\pi(x)$ is received, and the process continues, with discounted expected payoff $\beta \int v_\sigma(x') P(x, \diff x')$. This is the second term in (1.6). In what follows we call $v_\sigma$ the $\sigma$-value function.

Let $\Sigma$ be the set of all policies, defined as all $\bB$-measurable functions mapping $\Xsf$ to $\{0,1\}$. For each $\sigma \in \Sigma$, let $v_\sigma$ be the function defined recursively in (1.6). We can use the Neumann series lemma to show that $v_\sigma$ is uniquely defined in $b\Xsf$. Alternatively, we can introduce the operator $T_\sigma \colon b\Xsf \to b\Xsf$ via

We call $T_\sigma$ the policy operator defined by $\sigma$. In operator form it can be expressed as

Evidently, $v_\sigma$ solves (1.6) if and only if $v_\sigma$ is a fixed point of $T_\sigma$.

One easily shows that $T_\sigma$ is contracting (see Section A.2.2.2 for the definition) on the complete space $(b\Xsf, \| \cdot\|)$, where $\| \cdot \|$ is the supremum norm, defined by $\| f \| = \sup_{x \in \Xsf} |f(x)|$ for all $f \in b\Xsf$. Indeed, for arbitrary $v, w \in b\Xsf$,

where the absolute value $| \cdot |$ is applied pointwise (and the last inequality is by the triangle inequality for integrals --- or, if you prefer, by the inequality for positive operators in Exercise A.41 on page ). From the last expression we get

Taking the supremum over the left-hand side, we find that $T_\sigma$ is a contraction of modulus $\beta$ on $b\Xsf$. Hence, the $\sigma$-value function $v_\sigma$ is the unique fixed point of $T_\sigma$ in the candidate space $b\Xsf$.

Figure 1.3 shows the value functions $v_\sigma$ and $v_\tau$ for two possible policies $\sigma$ and $\tau$. The policies are shown on the left and the value functions are on the right. The environment is the same as Figure 1.2 with $\beta$ set to 0.96. The first policy $\sigma$ sells when the state is below 1.0 and continues otherwise. The second policy $\tau$ oscillates between selling and continuing. Each value function is computed as the fixed point of the corresponding policy operator in $b\Xsf$. The horizontal dashed line indicates the sale price $s$. In terms of value, policy $\tau$ is outperformed by $\sigma$ everywhere on the state space.

Now let’s consider optimality. A policy $\sigma$ is called optimal if $v_\tau(x) \leq v_\sigma(x)$ for all $\tau \in \Sigma$ and all $x \in \Xsf$. The value function $\vmax$, sometimes called the optimal value function, is defined by

Evidently $\sigma$ is an optimal policy if and only if $v_\sigma = \vmax$.

The problem of finding an optimal policy appears nontrivial, since $\Sigma$ is a large set whenever $\Xsf$ is large. Indeed, each $\sigma \in \Sigma$ is just an indicator function of a measurable set, so the cardinality of $\Sigma$ is the same as $\bB$. However, it turns out that we can find, characterize, and compute optimal policies relatively easily, using the theory of dynamic programming. In particular, we can state the following result, which is proved below in Section 1.1.1.4.

Theorem 1.1.1 is a simple consequence of Richard Bellman’s (1920--1984) beautiful theory of dynamic programming Bellman, 1957. Equation (1.12) is called the Bellman equation.

The characterization in (1.13) has the following natural interpretation. The expression $\pi(x) + \beta \int \vmax(x') P(x, \diff x')$ is the payoff (expected present value) for choosing to continue, receiving current profits, and then behaving optimally (since we are valuing future states with $\vmax$). The best decision at $x$ is to continue if this is larger than $s$, which is achieved by setting $a=0$. Otherwise the manager should set $a=1$ and stop.

We shall repeatedly use a term related to Theorem 1.1.1. Thus, given $v \in b\Xsf$, we will agree to say that $\sigma \in \Sigma$ is $v$-greedy whenever

With this terminology, we can repeat the policy optimality characterization in Theorem 1.1.1 by saying that a policy is optimal if and only if it is $\vmax$-greedy. This idea is a cornerstone of our theory.

1.1.1.3The Bellman Operator¶

We noted above that a policy is optimal if and only if it is $\vmax$-greedy. This provides a direct avenue for computing optimal policies: First calculate $\vmax$ and then take a $\vmax$-greedy policy. A straightforward way to approximate $\vmax$ is to iterate on the Bellman operator, which, in the present setting, is the self-map $T$ on $b\Xsf$ defined at $v \in b\Xsf$ by

In operator-theoretic notation, we write $T$ as $Tv = s \vee (\pi + \beta Pv)$. Evidently $v$ solves the Bellman equation if and only if $v$ is a fixed point of $T$.

Note that $T$ is a contraction of modulus $\beta$ on $(b\Xsf, \| \cdot \|)$. Indeed, fixing $v, w \in b\Xsf$ and applying the elementary bound

we get

The rest of the argument is identical to the one for contractivity of $T_\sigma$ in Section 1.1.1.2.

From this and Theorem 1.1.1, we see that $T$ has a unique fixed point in $b\Xsf$ and that the fixed point is the value function $\vmax$. Moreover, for any $v$ in $b\Xsf$, we have $T^k v \to \vmax$ as $k \to \infty$. In other words, fixed point iteration (also called successive approximation) allows us to approximate $\vmax$ arbitrarily well.

Figure 1.4 shows an approximate optimal policy and an approximation to the value function $\vmax$. The latter was computed by iterating with the Bellman operator $T$ from initial condition $v_0 \equiv 0$ and monitoring for convergence (waiting for the step sizes $\| T^k v_0 - T^{k+1} v_0 \|$ to fall below some threshold). We then took the resulting function $v$ and computed a $v$-greedy policy. We used the same parameters as in Figure 1.3. The optimal policy has a threshold structure: the manager sells the firm when the state is below a critical value and continues operating otherwise. The value function $\vmax$ dominates the sale price $s$ everywhere, reflecting the value of the option to wait and sell later.

1.1.1.4Proving Theorem 1.1.1¶

In this book we will prove far more general results than Theorem 1.1.1. So providing an immediate proof of the theorem here is actually redundant and postpones our presentation of some sample applications. Nevertheless, we now sketch a short proof of Theorem 1.1.1, but alert readers that they can safely move on without digesting it now.

1.1.1.5How About More General Policies?¶

Up to now we have focused on stationary Markov policies, which, in our language, are measurable maps from $\Xsf$ to $\{0,1\}$. Restricting our attention to such policies prevents the manager from making decisions based on a longer history of states and actions, or from changing policies at some date. We have also ignored the possibility that the manager might wish to randomize actions, meaning that the choice is a probability of selling, rather than a fixed selection from $\{0,1\}$.

It turns out that focusing exclusively on stationary Markov policies is appropriate in the current setting. We show in Section 3.1.4 that allowing nonstationary policy choices cannot lead to higher expected present value, and that this result holds far more generally. Moreover, randomization cannot improve outcomes in this setting. For a proof in a similar environment, see our discussion of mixed strategies in Section 9.2.1.6 of Sargent & Stachurski (2025).

1.1.2Extensions¶

The theory stated so far is elegant and can be extended in some directions with relatively little effort. For example, we can ask the manager to control inventories, capital stocks, and the size and disposition of a labor force across tasks. The same fundamental ideas still govern optimality, and the same solution approaches still work.

But some extensions are more challenging and require moving beyond standard dynamic programs. We describe some of these challenges next.

1.1.2.1Beyond Constant Discount Rates¶

One restrictive assumption in Section 1.1.1 is that the discount factor $\beta$ is constant. In fact discount rates vary considerably. For example, market interest rates fluctuate substantially, responding to changes in monetary policy, inflation expectations, and risk premia. Interest rates charged to risky borrowers can fluctuate even more widely than benchmark rates. For a firm weighing the decision to continue operating versus exiting, the cost of capital at which future profits are discounted will have a substantial impact on optimal decisions. In practice, firms routinely incorporate time-varying discount rates into their strategic planning.

Figure 1.5 illustrates the extent of this variation using US data from the Federal Reserve. The top panel shows the federal funds rate, which transmits to firm financing costs through the credit channel. The bottom panel plots the real interest rate, computed as the 10-year Treasury yield minus twelve-month CPI inflation. Both sets of rates affect the intertemporal tradeoffs that firms face: when rates are high, future profits are discounted more heavily, reducing the present value of long-lived investments and making exit or disinvestment more attractive. Conversely, low or negative rates reduce the cost of waiting and encourage firms to invest, expand capacity, or delay exit from declining markets. The relative importance of real vs nominal rates varies across firms. The swings visible in Figure 1.5 underscore the issues with assuming a fixed discount factor $\beta$ when studying intertemporal choices of firms.

To accommodate dependence of discount factors on firm-specific or macroeconomic variables, we can specify that $\beta = b(X_t)$ for some suitable function $b$. Fortunately, this modification can be accommodated in the current setting. A discussion can be found in Section 4.2.1.3. But the associated theory can become more complicated when the controller’s actions affect state components that affect the discount factor. This happens, for example, in models of firms who face higher borrowing costs because they pursue high-risk strategies that involve occasionally running down their cash reserves. That makes the dynamic programming problem more challenging, particularly if we assume that interest rates are occasionally negative; such cases break contractivity properties of policy and Bellman operators. Optimality results for the finite state case can be found in Sargent & Stachurski (2025). We study more general cases in Chapter 6.

1.1.2.2Unbounded Rewards¶

Another---more technical---issue with our analysis in Section 1.1.1 is that $\pi$ is bounded. This directly embeds the problem in the space of bounded functions $b\Xsf$ and pairs naturally with the supremum norm. The contraction and optimality proofs unfold smoothly when working in such an environment. But assuming that $\pi$ is bounded can be overly restrictive.

It turns out that we can drop the boundedness assumption without too much difficulty. One way is to assume instead that $\| \pi \|_\ell < \infty$ where $\ell \colon \Xsf \to [1, \infty)$ and $\| \cdot \|_\ell$ is the $\ell$-weighted norm defined by $\| f \|_\ell \coloneq \sup_{x \in \Xsf} |f(x)|/\ell(x)$. This approach is discussed in Section 7.2.2.2.

Another option is to embed the problem in the class of integrable functions $L_1(\psi) \coloneq L_1(\Xsf, \bB, \psi)$ for a suitable measure $\psi$ on $(\Xsf, \bB)$. (For background see Section A.4.2.4.) For example, suppose that $\psi$ is a stationary distribution (see Section A.5.4.4) of the stochastic kernel $P$ and that $\pi \in L_1(\psi)$. The policy operators then send $L_1(\psi)$ into itself. Indeed, if $\pi \in L_1(\psi)$ and we fix $v \in L_1(\psi)$, then $|T_\sigma \, v| \leq |s| + |\pi| + \beta |P v|$, so $T_\sigma \, v$ is in $L_1(\psi)$ when $Pv$ is $\psi$-integrable. This is true by stationarity of $\psi$ --- see (i) of Lemma A.5.32 and the surrounding discussion. Moreover, $T_\sigma$ is a contraction map on $L_1(\psi)$, as can be seen by integrating both sides of the bound $|T_\sigma \, v - T_\sigma \, w| \leq \beta P | v - w|$ with respect to $\psi$ and using (A.102) on p.  to obtain $\int P | v - w| \diff \psi = \int |v - w| \diff \psi$. One can also show that the Bellman operator $T$ is a contraction with respect to the norm on $L_1(\psi)$ and then proceed to adapt proofs in Theorem 1.1.1.

Rather than provide all details here, we defer further discussion to Section 4.2.1.2.

1.1.3Beyond Risk Neutrality¶

A limitation of the preceding analysis is how it treats risk. We assumed that the manager wants to maximize the expected present value of cash flow generated by the firm across different strategies (policies). But what if the manager wants something else?

Canonical theories of firm behavior suggest that expected present value is the appropriate criterion. In complete and frictionless markets, a firm’s shareholders can hedge firm-specific risks by trading other securities, so the firm’s manager should not worry about that Modigliani & Miller, 1958Smith & Stulz, 1985. But maybe financial markets are incomplete and maybe shareholders lack enough information about risks or financial sophistication to develop optimal hedging strategies. Maybe managers’ incentives are not aligned with shareholders’ interests. Managers might be concerned about a firm’s survival and overweight downside risks relative to shareholders. Indeed, various studies offer evidence for such risk-averse decision-making within both small and large firms (see, e.g., Graham et al. (2013), Kerr et al. (2019), or Almeida et al. (2024)).

In this section we consider adjusting the manager’s problem to incorporate some of these considerations.

1.1.3.1Distributions of Rewards¶

Let’s return to our jump-off point for optimization, where we decided to seek a policy that solves $\max_{\sigma \in \Sigma} v_\sigma(x)$ for all $x$. We know that $v_\sigma(x)$ is the expected lifetime value of policy $\sigma$ given initial condition $x$. As such, we can also write

where

Here $T(\sigma)$ is the date at which the firm is sold at price $s$ (with convention $\inf \varnothing = \infty$, so that $T(\sigma)=\infty$ if the firm is never sold). Evidently $Z_\sigma$ is a random payoff, depending on the policy and the random path $(\pi_t)_{t \geq 0}$. The random variable $Z_\sigma$ depends on the initial state $x$ but we have chosen to suppress this in the notation.

The left-hand subfigure in Figure 1.6 shows the distribution of $Z_{\sigopt}$, lifetime value under the optimal policy $\sigopt$, computed by fixing an initial condition $x$, simulating 100,000 profit paths from a given initial state, and then computing the discounted payoff along each path. (Parameter values were the same as in Figure 1.3.) The mean of the distribution is $v_{\sigopt}(x)$, which is also $\vmax(x)$. The policy is regarded as optimal because the mean of the distribution is larger than the mean of $Z_{\sigma}$ under any other policy, and given any other initial condition $x$. The right-hand subfigure compares $Z_{\sigopt}$ with $Z_\sigma$, where $\sigma$ is the policy that never sells.

Let’s consider these distributions from the perspective of firm managers when markets are not frictionless, and information is not perfect. In this case, as discussed at the start of Section 1.1.3, managers care about more than just the mean of these distributions. While the mean will surely be of interest, these managers are likely to also care about factors such as variance, upside risk and downside risk. Let’s now consider how we might insert preferences over such factors into our model.

1.1.3.2Distributional Dynamic Programming¶

Some researchers have begun to construct a theory of “distributional dynamic programming” where the core idea is to track the distribution of the payoff across policies and initial conditions. In our context, this means choosing $\sigma$ so that $Z_\sigma$ has an “optimal” distribution. For example, a manager might want a distribution with a relatively high mean and low downside risk. Bellemare et al. (2023) show that, for a relatively broad class of dynamic programming problems, a distributional version of the Bellman equation can be constructed, where the left- and right-hand sides of the Bellman equation are both distributions. We formalize this idea within the abstract dynamic programming framework in Section 2.3.4.

In practice, the theory of distributional dynamic programming is constrained by the fact that there is no natural extension of the idea of a greedy policy to the setting of distributional Bellman equations. As such, we focus on environments where agents are able to specify loss or reward functions over distributions. The next few sections investigate such cases, while still preserving concern for tail properties and additional moments beyond the mean.

1.1.3.3Mean-Variance Analysis¶

Let $R$ be a random payoff that we want to evaluate. Mean-variance analysis proposes the criterion $\EE [R] - (\gamma/2) \var[R]$, where $\gamma$ parameterizes risk-aversion. In the context of our manager’s problem, the mean-variance criterion tells us to solve

Assuming that the initial condition is $x$, the first term $\EE [Z_\sigma]$ is just $v_\sigma(x)$. The second term is harder to calculate but its role is clear: it downweights policies that generate high variance payoffs, with the extent of downweighting depending on the size of $\gamma$. More risk averse managers will use larger values of $\gamma$ and their preferred policies will deviate more from what we previously defined to be optimal---that is, the policy that solves $\max_{\sigma \in \Sigma} v_\sigma(x) = \max_{\sigma \in \Sigma} \EE Z_\sigma$ for all $x$.

1.1.3.4Alternatives to Mean-Variance¶

The mean-variance criterion is not the only way to formulate concerns about risk. An alternative formulation solves

Here $\EE$ again denotes the mathematical expectation with respect to the probability distribution of the random payoff, which the decision maker is assumed to know. The map $e_\gamma$ is called an entropic certainty equivalent. The parameter $\gamma$ parameterizes risk aversion. When $\gamma > 0$, the decision maker values $Z_\sigma$ below $\EE[Z_\sigma]$. We say that risk aversion is higher when $\gamma$ is larger. An introduction to these ideas is provided in Section 7.2.2 of Sargent & Stachurski (2025).

The entropic criterion is attractive for several reasons. One is that, with sufficiently many finite moments, a Taylor expansion produces

where $\kappa_n$ is the $n$-th cumulant

This tells us that, with positive $\gamma$, the agent likes a high mean, dislikes variance, likes positive skewness (right tails), dislikes kurtosis (fat tails), etc. When higher moments are small we get

which connects us back to mean-variance analysis. The approximation above becomes exact when $Z_\sigma$ is normally distributed.

In addition, the entropic criterion can be regarded as an indirect utility function that emerges from a setting in which the manager doubts its probability model for $R$. In particular, let $P$ denote the manager’s baseline model probability measure for the payoff $Z_\sigma$. Then it can be shown that

where the minimum is over probability measures $Q$ absolutely continuous with respect to $P$ and $D_{KL}(Q \| P) \coloneq \EE_Q [\ln(\diff Q / \diff P)]$ is a Kullback--Leibler statistical divergence for measuring the discrepancy between two probability distributions. Here the parameter $1/\gamma$ controls the size of a penalty that the minimizer pays for distorting $Q$ relative to baseline probability model $P$; larger $\gamma$’s allow the minimizing “player” who chooses $Q$ to range over a larger set of alternative models. Such an analysis connects entropic preferences to robust control and ambiguity aversion and will be discussed in Chapter 7.

The entropic criterion $e_\gamma(Z_\sigma)$ is a special case of a more general objective

where $\phi$ is a given function. Typically $\phi$ is concave, as is the case for $\phi(x) = \exp(-\gamma x)$ when $\gamma > 0$. Another example is the Kreps--Porteus expectation, which is obtained by setting $\phi(x) = x^{1-\gamma}$.

A third option for inserting preferences over risk is to evaluate

where $\alpha \in [0,1]$ is a given constant. This objective is called value-at-risk and can be understood as the smallest cash injection $c$ such that the probability of a net loss is no more than $\alpha$. Intuitively, if $Z_\sigma$ has more downside risk, then $\VaR_\alpha(Z_\sigma)$ increases, as more cash is needed to keep the loss probability below the threshold. Thus, a manager seeking a low-risk policy might look to minimize $\VaR_\alpha(Z_\sigma)$, or, equivalently, to solve $\max_\sigma - \VaR_\alpha(Z_\sigma)$.

Value-at-risk became industry standard in the 1990s, partly due to popularization through RiskMetrics, a risk management framework developed at J.P. Morgan. It has spawned a variety of alternatives and extensions, including conditional value-at-risk, entropic value-at-risk and relativistic value-at-risk. We will meet some of these ideas again in Chapter 7.

1.1.3.5Difficulties¶

While the risk-management concepts discussed above are all sensible, they complicate solving for an optimal policy because they make the objective be nonlinear. For example, consider the mean-variance problem (1.24), which we can write as

The function $m_V$ is nonlinear due to the presence of the variance term, and this nonlinearity prevents us from passing $m_V$ through the sum and thereby deriving a recursive expression for the value of a strategy similar to (1.6). To see this, recall the role that linearity of the expectations operator $\EE_t$ played in our derivation of representation (1.4).

Bellman’s dynamic programming theory requires having a recursive representation for valuations under alternative strategies. Without that, numerical strategies for solving global optimization problems like $\max_\sigma U(Z_\sigma)$ can be poorly behaved, very high dimensional, and virtually inaccessible to the theory of dynamic programming.

Even worse, there is an important sense in which the criterion of maximizing $m_V(Z_\sigma)$ over $\sigma \in \Sigma$ is no longer the right one, since there is no guarantee that the best strategy for the manager is to choose a stationary Markov policy and apply it in every period. For example, in our new nonlinear setting, it might be optimal for the manager to apply a given policy $\sigma$ in the first period and a second policy $\tau$ in all periods thereafter (see, e.g., Section 5 of Bäuerle & Jaśkiewicz (2024)). While this might still seem feasible---we need only to compute one more policy--- time inconsistency arises. The manager must be committed to switching to $\tau$ in the second period, since re-optimization would lead to choosing $\sigma$ again.

Unfortunately none of the alternatives to mean-variance analysis discussed in Section 1.1.3.4 offer a way out of the problem described above, since nonlinearity in the objective again prevents construction of a recursive representation. As with mean-variance, this lack of recursivity requires deploying dynamic programs in new ways.^[1]

1.1.3.6Back to Recursion¶

In Section 1.1.3.5, we saw how nonlinearity intended to capture risk-preferences led to a breakdown of dynamic programming theory. Fortunately, there is a way to inject nonlinearity and risk-preferences into the manager’s problem without breaking recursivity and hence access to the core ideas of dynamic programming. The idea is to stop trying to apply risk-preferences directly to the net present value sum and instead apply them period-by-period. We can do this by starting with the risk-neutral recursive valuation (1.6) and modifying it to

where $K$ is a possibly nonlinear operator from $b\Xsf$ to itself. For example, using the notation $(Pv)(x) = \int v(x') P(x, \diff x')$, we can set

to implement the mean-variance criterion, or

for entropic risk preferences.

This alternative approach to inserting risk preferences into the manager’s problem is somewhat less intuitive than the direct approach that we reviewed in Section 1.1.3.3 and Section 1.1.3.4. In addition, it introduces a new problem: is $v_\sigma$ actually well-defined by the nonlinear functional equation (1.33)? On the other hand, it offers a major advantage: provided we can show that $v_\sigma$ is in fact well-defined --- which is a problem for fixed point theory --- the valuations are recursive by construction. Exploiting this fact, we can extend Bellman’s original theory in very natural ways. This is one of the main subjects of this book.

We will attack this problem in stages, beginning with an abstract recursive setup in Chapter 2. The setup will be recursive in the sense that each valuation $v_\sigma$ will be represented as the fixed point of a possibly nonlinear policy operator $T_\sigma$. Our approach will then be to rewrite Bellman’s optimality theory in this abstract setting and seek properties on the policy operators under which the main results go through. At the end of this process we will connect back to the applications from this chapter.

Before progressing to this abstract theory, we look at some other concrete examples, beginning with finite state Markov decision processes.

1.2Finite MDPs¶

Finite state Markov decision processes (MDPs) form the foundations of many quantitative modeling and reinforcement learning routines, as well as providing a benchmark setting for dynamic programming theory (see, e.g., Puterman (2005) or Chapter 5 of Sargent & Stachurski (2025)). In this section we introduce finite state MDPs and some extensions. As was the case for the firm problem considered in Section 1.1, our main objective is to introduce a class of dynamic programming problems that will motivate the abstract theory starting in Chapter 2.

While the presentation below is self-contained, readers wanting a slower pace and more examples might prefer to begin with Chapter 5 of Sargent & Stachurski (2025).

1.2.1Theory¶

In this section we introduce the finite MDP framework and state core optimality results---the Bellman equation and the greedy policy characterization of optimal policies. We then present three fundamental algorithms: value function iteration, Howard policy iteration, and optimistic policy iteration. We illustrate the main ideas with an application to firm cash management.

1.2.1.1The Discrete Time Model¶

A finite state Markov decision process (finite MDP) consists of

• a finite set $\Xsf$ called the state space,

• a finite set $\Asf$ called the action space,

and a tuple $(\Gamma, r, \beta, P)$, where

• $\Gamma$ is a nonempty correspondence from $\Xsf$ to $\Asf$, which in turn defines the feasible state-action pairs

  $$\Gsf \coloneq \setntn{(x, a) \in \Xsf \times \Asf}{a \in \Gamma(x)},$$

  (1.36)

• a reward function $r \colon \Gsf \to \RR$,

• a discount factor $\beta$ in $[0,1)$, and

• a stochastic kernel $P$ from $\Gsf$ to $\Xsf$, which provides transition probabilities for the next period state given current state and action.

Since $P$ is a stochastic kernel, it satisfies $\sum_{x'} P(x, a, x') = 1$ for all $(x,a) \in \Gsf$.

Given an initial condition $X_0 = x$, the objective is to maximize the expected discounted sum

Here $(X_t)_{t \geq 0}$ takes values in $\Xsf$ and $(A_t)_{t \geq 0}$ takes values in $\Asf$. After observing state $X_t$, the controller chooses action $A_t$ from the feasible set $\Gamma(X_t)$ and the new state $X_{t+1}$ is drawn from the distribution $P(X_t, A_t, \cdot)$. The constant $\beta \in [0,1)$ is a discount factor and $r$ is a reward function. In maximizing this objective, the action sequence $(A_t)$ must also satisfy an information constraint: Each $A_t$ is required to be measurable with respect to the $\sigma$-algebra generated by $(X_0, \ldots, X_t)$. Thus, the controller can use information from the past and present but not the future.

As was the case for the firm problem in Section 1.1, it turns out that actions depending on all of $(X_0, \ldots, X_t)$ are no better than actions that depend only on $X_t$. We will show this formally in Section 3.1.4. As a result, we focus on stationary Markov policies, where the same deterministic function of the state is applied at every point in time. We call such stationary Markov policies feasible policies, the set of which is given by

For each $\sigma \in \Sigma$, we set

It follows from our assumptions on $P$ that $P_\sigma$ is a stochastic matrix, meaning that $P_\sigma \geq 0$ and all rows sum to one. By choosing a policy $\sigma$, the controller determines a reward function $r_\sigma$ on the state and Markov dynamics $P_\sigma$ for the state process. Following notation in Section A.5.4, we write

interpreting this value as the expectation of $h(X_{t+1})$ when $X_t = x$ and the controller uses policy $\sigma$.

The lifetime value of $\sigma$ given $X_0 = x$ is

when $(X_t)_{t \geq 0}$ is a Markov chain generated by $P_\sigma$ with initial condition $X_0 = x \in \Xsf$. Since $\EE \, r_\sigma(X_t) = (P_\sigma^t r_\sigma)(x)$, the function $v_\sigma$ can be expressed pointwise on $\Xsf$ as

where $I$ is the identity map on $\RR^\Xsf$, the set of real-valued functions on $\Xsf$. This representation on the right-hand side is essentially the same as (1.5). In particular, the second equality comes from the Neumann series lemma (page ). See also Puterman (2005), Theorem 6.1.1, or Chapter 5 of Sargent & Stachurski (2025).

The policy operator associated with given $\sigma$ for the finite MDP model takes the form

1.2.1.2Core Optimality Results¶

The definition of the value function is the same as that for the firm problem in Section 1.1.1.2:

Similarly, a policy $\sigma \in \Sigma$ is called optimal if $v_\tau \leq v_\sigma$ for all $\tau \in \Sigma$.

The Bellman equation for this problem is

This is a functional equation that restricts $v \in \RR^\Xsf$. The Bellman operator is given by

By construction, $v$ solves the Bellman equation if and only if $v$ is a fixed point of the Bellman operator. In the next exercise, $d_\infty(f, g) \coloneq \sup_{x \in \Xsf}|f(x) - g(x)|$. Corollary A.5.13 may be helpful.

We say that $\sigma \in \Sigma$ is $v$-greedy if

We can now state the following optimality result, which naturally mirrors our previous result for the firm problem (Theorem 1.1.1).

A full proof of Theorem 1.2.1 can be found in Chapter 5 of Sargent & Stachurski (2025). The proof is almost identical to that of Theorem 1.1.1, which we provided for the firm problem. We will also prove Theorem 1.2.1 in Section 2.3.3.2, as a special case of far more general results.

The next obvious step is to use the results in Theorem 1.2.1 to compute optimal policies. Next we consider algorithms designed for this purpose.

1.2.1.3Algorithms¶

The three most important algorithms for solving dynamic programming problems are value function iteration (VFI), Howard policy iteration, and optimistic policy iteration (OPI). In the present setting, they take the forms of Algorithm 1.2.1, Algorithm 1.2.2, and Algorithm 1.2.3.

VFI amounts to iterating $k$ times with $T$ from some initial condition $v \in V$ (where $k$ is determined by a fixed tolerance level for error), producing an approximation $v_k \coloneq T^k v$ to $\vmax$, and then computing a $v_k$-greedy policy $\sigma$. This idea is natural, given that $\vmax$-greedy policies are optimal, since $T$ is a contraction mapping and $\vmax$ is the unique fixed point (so that $v_k$ is close to $\vmax$).

In HPI, one begins with a guess $\sigma$ of the optimal policy and then iterates between computing the lifetime value of that policy (as given in (1.42)) and the corresponding greedy policy. In fact HPI is equivalent to Newton fixed point iteration applied to the Bellman operator. See, for example, Chapter 5 of Sargent & Stachurski (2025).

OPI can be thought of as a “convex combination” of VFI and HPI. Instead of computing the lifetime value $v_\sigma = (I - \beta P_{\sigma})^{-1} r_{\sigma}$ of current policy guess $\sigma$, one computes instead $T_{\sigma}^m v$, which is an approximation to $v_\sigma$ (since $T_\sigma$ is a contraction with fixed point $v_\sigma$). There are two edge cases:

1. If $m$ is large, this approximation is tight, and hence OPI is close to HPI.

2. If $m=1$, OPI reduces to VFI.

OPI usually outperforms both VFI and HPI for some intermediate values of $m$. Further intuition and discussion is provided in Chapter 5 of Sargent & Stachurski (2025).

For the finite MDP setting, we can state the following results:

We shall prove these results after we discuss convergence of these algorithms in a general setting in Section 2.2.1.

1.2.1.4Solving MDPs via Linear Programming¶

Many dynamic programs can be formulated as linear programs. We illustrate with finite MDPs. To do so, we recall that a typical linear program has the form

Here $c$ is a vector in $\RR^n$, the term $\inner{c,v}$ is the inner product $\sum_i c_i v_i$, $A$ is a matrix with $n$ columns and $b$ is a vector with the same length as $Av$. (Other LP formulations replace the inequality $Av \leq b$ with $Av = b$ or $Av \geq b$, or a mix of inequality and equality constraints. Standard LP algorithms and theory can be applied to all of these cases.)

To place the finite state MDP from Section 1.2.1.1 into this framework, we begin by setting

where $T$ is the Bellman operator. Recalling that $\vmax$ represents the value function, we have the following result:

Now let $c$ be an everywhere positive element of $\RR^\Xsf$ and consider the linear program

Here $\inner{c, v} = \sum_x c(x) v(x)$ and the minimization is over all $v \in \RR^\Xsf$ that satisfy the stated constraint. As before, we require that $c$ is everywhere positive. Evidently (1.52) takes the form of (1.50) after suitable assignment of indices. Thus, (1.52) is a linear program. This leads us to

Proposition 1.2.4 implies that we can compute the value function and hence solve the MDP using linear programming techniques. The LP approach is useful for many models, such as those that incorporate additional linear constraints, e.g., bounds on expected rewards and resources, that are difficult to handle with iterative methods. On the other hand, the number of constraints in (1.52) equals $|\Gsf|$, which can be large, so iterative methods are still often preferred. See Section 1.6 for references and further discussion.

1.2.1.5Example: Cash Management¶

To illustrate finite MDPs in a concrete setting, we now study a cash management problem faced by a firm that must balance cash holdings against returns from securities. This problem dates back to the work of Baumol (1952) and Tobin (1956), who developed inventory-theoretic models of the demand for money. In their models, the decision maker decides how much cash to hold versus interest-bearing assets, balancing the opportunity cost of holding idle cash against the transaction costs of converting assets to cash.

The decision maker manages fixed total wealth $\bar w$, which is divided between cash holdings $x$ and securities $s = \bar w - x$. Each period, the decision maker experiences random portfolio shocks and must decide whether to transfer funds between cash and securities. The decision maker earns returns on securities but pays transaction costs for transfers and faces penalties for insufficient cash. (Assuming that wealth is fixed allows us to get by tracking only $x$, and not $s$.)

The state space for cash is $\Xsf = \{0, 1, \ldots, \bar w\}$. At state $x$, the feasible actions are transfers $a$ satisfying $0 \leq x+a \leq \bar w$. Thus, $\Gamma(x) = \{a \in \ZZ \mid -x \leq a \leq \bar w - x\}$. Portfolio shocks (cash payments, equity payments, debt restructuring, etc.) are iid, written as $(\xi_t)_{t \geq 1}$, and take values in a set $\Xi = \{-k, \ldots, k\}$ with probability mass function $\phi$. Transition probabilities are determined by the next-period state

where the max and min keep $x'$ in the state space. The transition probabilities are, therefore,

Flow profits are given by

Here $\rho$ is the rate of return on securities, $c$ is a fixed transaction cost, $\tau$ is a proportional transaction cost, and $p$ is a penalty for insufficient cash (in this case, when $x + a + \xi < 0$). To fit the problem into the MDP framework, we take expectations of flow profits to get the period reward

Future payoffs are discounted using discount factor $\beta$.

The set of feasible policies $\Sigma$ is defined from $\Gamma$ in the usual way (see (1.38)). The lifetime value of any given policy can be computed from $v_\sigma = (I - \beta P_\sigma)^{-1} r_\sigma$, as discussed in Section 1.2.1.1. Figure 1.7 illustrates by using this formula to compute $\sigma$-value functions for two policies. The first is a “do nothing” policy that sets $a = 0$ for all states. The second is a target policy that always moves toward a fixed target cash level. As we will see, both policies are suboptimal.

Next let’s solve for an approximately optimal policy using VFI, as described in Algorithm 1.2.1. Figure 1.8 shows the resulting (approximately) optimal policy and value function. The policy shows the optimal transfer amount as a function of current cash holdings, while the value function shows the lifetime value of following the optimal policy. Here we set total wealth $\bar w = 50$, return on securities $\rho = 0.02$, fixed transaction cost $c = 1$, proportional transaction cost $\tau = 0.1$, penalty for insufficient cash $p = 10$, and $\beta = 0.95$. The cash flow shocks are uniformly distributed on $\{-5, -4, \ldots, 4, 5\}$.

The optimal policy recommends that when cash holdings are low, the decision maker should move funds from securities to cash (take a positive action), and when cash holdings are high, move funds from cash to securities (a negative action). The value function declines for large cash balances because wealth is fixed and hence high cash balances mean low holdings of securities and reduced returns.

Figure 1.9 shows iterates for the policy sequence and the value sequence under the HPI algorithm. The initial policy is a do-nothing policy. As mentioned in Theorem 1.2.2, HPI converges in a finite number of iterations. Here it converges in 5 iterations, so the last policy is the exact optimal policy (modulo floating point arithmetic), and the last $\sigma$-value function is the value function $\vmax$. The gap between the first value function associated with the do-nothing policy, and the final value function associated with the optimal policy, is value of active cash management. This gap is largest at extreme cash levels, where the do-nothing policy either leaves the firm exposed to cash shortfalls or forgoes returns on securities.