8 Recursive Decision Processes

While the MDP model from Chapter 5 and Chapter 6 is elegant and widely used, researchers in economics, finance, and other fields are working to extend it. Reasons include:

1. MDP theory cannot be applied to settings where lifetime values are described by the kinds of nonlinear recursions discussed in Chapter 7.

2. Equilibria in some models of production and economic geography can be computed using dynamic programming but not all such programming problems fit within the MDP framework.

3. Dynamic programming problems that include adversarial agents to promote robust decision rules can fail to be MDPs.

To handle such departures from the MDP assumptions, we now construct a more general dynamic programming framework, building on an approach to optimization initially developed by Denardo (1967) and extended by Bertsekas (2022). Further references are provided in Section 8.4.

We start this chapter by building a framework that centers on an abstract representation of the Bellman equation (Section 8.1). We then state optimality results and show how they can be verified in a range of applications. We defer proofs of core optimality results to Chapter 9, where we strip dynamic programs down to their essence by adopting a purely operator-theoretic perspective.

8.1Definition and Properties¶

In this section, we introduce and analyze optimality conditions for recursive decision processes that include and extend all dynamic programming frameworks discussed so far. Throughout this chapter, $\Xsf$ denotes a finite set.

8.1.1Defining RDPs¶

Consider a generic Bellman equation of the form

Here $x$ is the state, $a$ is an action, $\Gamma$ is a feasible correspondence, and $B$ is an “aggregator” function. We understand $\Gamma(x)$ as all actions available to the controller in state $x$. The function $v$ assigns values to states and is a member of some class $V \subset \RR^\Xsf$. This “abstract” Bellman equation generalizes all of the Bellman equations presented in previous chapters.

Our plan is to analyze the Bellman equation (8.1) and state conditions on $B$ and the other primitives that make strong optimality properties hold. As a first step, we introduce two finite sets,

• an action space $\Asf$ and

• a state space $\Xsf$.

Given $\Xsf$ and $\Asf$, we define a recursive decision process (RDP) to be a triple $\rR = (\Gamma, V, B)$ consisting of

1. a feasible correspondence $\Gamma$ that is a nonempty correspondence from $\Xsf$ to $\Asf$, which in turn defines

   • the feasible state-action pairs

- and the set of feasible policies

2. a subset $V$ of $\RR^\Xsf$ called the value space, and

3. a value aggregator $B$ that maps $\Gsf \times V$ to $\RR$ and satisfies both the monotonicity condition

and the consistency condition

Throughout, $\leq$ represents the pointwise order on $\RR^\Xsf$.

The definition of the feasible correspondence in (i) is identical to that for the MDP in Chapter 5. As for (ii), we understand $V$ to be a class of functions that assign values to states. In (iii), the interpretation of the aggregator $B$ is:

$B(x, a, v) =$ total lifetime rewards, contingent on current action $a$, current state $x$, and using $v$ to evaluate future states.

The monotonicity condition (8.4) is natural: if, relative to $v$, rewards are at least as high for $w$ in every future state, then the total rewards one can extract under $w$ should be at least as high. The consistency condition in (8.5) ensures that as we consider values of different policies we remain within the value space $V$.

The MDP framework is a special case of the RDP framework:

The last example is a special case of Example 8.1.1, since the cake eating problem is an MDP (see Section 5.1.2.3). Nonetheless, Example 8.1.2 is instructive because, for cake eating, the MDP construction is tedious (e.g., we need to define a stochastic kernel $P$ even though transitions are deterministic), while the RDP construction is straightforward.

The next example makes a related point.

Example 8.1.1--Example 8.1.4 treated RDPs that can be embedded into the MDP framework. In the remaining examples, we consider models that cannot be represented as MDPs.

Example 8.1.8 is a minimization problem. We treat minimization explicitly in Section 8.3.5, although the shortest path setting can be converted maximization by replacing $c(x,x')$ with $-c(x,x')$. This produces an application similar to the cake eating problem in Example 8.1.2 (although discounting is eliminated and network structure shows up in the constraint).

8.1.2Lifetime Value¶

We aim to discuss optimality of RDPs. To prepare for this topic, we now clarify lifetime values associated with different policy choices in the RDP setting.

8.1.2.1Policies and Value¶

Let $\rR = (\Gamma, V, B)$ be an RDP with state and action spaces $\Xsf$ and $\Asf$, and let $\Sigma$ be the set of all feasible policies. For each $\sigma \in \Sigma$ we introduce the policy operator $T_\sigma$ as a self-map on $V$ defined by

The RDP policy operator is a direct generalization of the MDP policy operator defined, as well as the optimal stopping policy operator defined.

Consider a given RDP $(\Gamma, V, B)$ and fix $\sigma \in \Sigma$. If $T_\sigma$ has a unique fixed point in $V$, we denote this fixed point by $v_\sigma$ and call it the $\sigma$-value function. It is natural to interpret $v_\sigma$ as representing the lifetime value of following policy $\sigma$.

The previous examples are linear but the same idea extends to nonlinear recursive preference models as well. To see this, recall the generic Koopmans operator $(Kv)(x) = A(x, (Rv)(x))$ introduced in Section 7.3.1. Lifetime value is the unique fixed point of this operator whenever it exists. In all of the RDP examples we have considered, the policy operator can be expressed as $(T_\sigma \, v)(x) = A_\sigma(x, (R_\sigma \, v)(x))$ for some aggregator $A_\sigma$ and certainty equivalent operator $R_\sigma$. Hence $T_\sigma$ is a Koopmans operator and lifetime value associated with policy $\sigma$ is the fixed point of this operator.

8.1.2.2Uniqueness and Stability¶

Let $\rR = (\Gamma, V, B)$ be a given RDP with policy operators $\{T_\sigma\}$. Given that our objective is to maximize lifetime value over the set of policies in $\Sigma$, we need to assume at the very least that lifetime value is well defined at each policy. To this end, we say that $\rR$ is well-posed whenever $T_\sigma$ has a unique fixed point $v_\sigma$ in $V$ for all $\sigma \in \Sigma$.

Let $\rR$ be an RDP with policy operators $\{T_\sigma\}_{\sigma \in \Sigma}$. In what follows, we call $\rR$ globally stable if $T_\sigma$ is globally stable on $V$ for all $\sigma \in \Sigma$.

Obviously, every globally stable RDP is well-posed.

In Section 8.1.3 we will see that global stability yields strong optimality properties.

8.1.2.3Continuity¶

Let $\rR = (\Gamma, V, B)$ be an RDP. We call $\rR$ continuous if $B(x, a, v)$ is continuous in $v$ for all $(x, a) \in \Gsf$. In other words, $\rR$ is continuous if, for any $v \in V$, any $(x, a) \in \Gsf$ and any sequence $(v_k)_{k \geq 1}$ in $V$, we have

Continuity is satisfied by all applications considered in this text. For example, for the RDP generated by an MDP (Example 8.1.1), the deviation $| B(x, a, v_k) - B(x, a, v)|$ is dominated by $\beta \| v_k - v \|_\infty$ for all $(x, a) \in \Gsf$. Hence continuity holds.

Below we will see that continuity is useful when considering covergence of certain algorithms.

8.1.3Optimality¶

In this section, we present optimality theory for RDPs.

8.1.3.1Greedy Policies¶

Given an RDP $\rR = (\Gamma, V, B)$ and $v \in V$, a policy $\sigma \in \Sigma$ is called $v$-greedy if

Since $\Gamma(x)$ is finite and nonempty at each $x \in \Xsf$, at least one such policy exists. As with policy operators, the notion of greedy policies extends existing definitions from earlier chapters.

Given RDP $\rR = (\Gamma, V, B)$, we say that $v \in V$ satisfies the Bellman equation if $v(x) = \max_{a \in \Gamma(x)}B(x,a,v)$ for all $x \in \Xsf$. The Bellman operator corresponding to $\rR$ is the map $T$ on $V$ defined by

8.1.3.2Algorithms¶

To solve RDPs for optimal policies, we use two core algorithms: Howard policy iteration (HPI) and optimistic policy iteration (OPI). As in previous chapters, OPI includes VFI as a special case.

To describe HPI we take $\rR = (\Gamma, V, B)$ to be a well-posed RDP with feasible policy set $\Sigma$, policy operators $\{T_\sigma\}$, and Bellman operator $T$. In this setting, the HPI algorithm is essentially identical to the one given for MDPs in Section 5.1.4.2, except that $v_\sigma$ is calculated as the fixed point of $T_\sigma$, rather than taking the specific form $(I-\beta P_\sigma)^{-1} r_\sigma$. The details are in Algorithm 8.1.

Algorithm 8.1 is somewhat ambiguous, since it is not always clear how to implement the instruction “$v_k \leftarrow$ the fixed point of $T_{\sigma_k}$”. However, if $\rR$ is globally stable, then each $T_{\sigma_k}$ is globally stable, so an approximation of the fixed point can be calculated by iterating with $T_{\sigma_k}$. This line of thought leads us to consider optimistic policy iterating (OPI) as a more practical alternative. Algorithm 8.2 states an OPI routine for solving $\rR$ that generalizes the MDP OPI routine in Section 5.1.4.

In Algorithm 8.2 we require that $v_0 = v_\sigma$ for some $\sigma \in \Sigma$. This assumption can be dropped in some settings. For practical purposes, however, it is almost always straightforward to initialize OPI with $v_0 = v_\sigma$ for some simple choice of $\sigma$.

When we turn to proofs, it will help to have an operator-theoretic description of HPI and OPI. To this end, we define two operators. The first is $\Hmax \colon V \to \{v_\sigma\}$, which is defined via

We call $\Hmax$ the Howard operator generated by $\rR$. Iterating with $\Hmax$ implements HPI. In particular, if we fix $\sigma \in \Sigma$ and set $v_k = \Hmax^k v_\sigma$, then $(v_k)_{k \geq 0}$ is the sequence of $\sigma$-value functions generated by HPI.^[1]

Next, fixing $m \in \NN$, we define the operator $W_m$ from $V$ to itself via

(See the previous footnote on the choice of $v$-greedy policies.) The operator $W_m$ is an approximation of $H$, since $T^m_\sigma v \to v_\sigma = Hv$ as $m \to \infty$. Iterating with $W_m$ generates the value sequence in OPI. More specifically, we take $v_0 \in \{v_\sigma\}$ and generate

This produces an infinite sequence of OPI value and policy iterates.

8.1.3.3Optimality¶

Let $\rR$ be a well-posed RDP with policy operators $\{T_\sigma\}$ and $\sigma$-value functions $\{v_\sigma\}$. In this context, we set $v^* \coloneq \bigvee_\sigma \, v_\sigma \in \RR^\Xsf$ and call $v^*$ the value function of $\rR$. By definition, $v^*$ satisfies

A policy $\sigma$ is called optimal for $\rR$ if $v_\sigma = v^*$; that is, if

Both of these definitions generalize the definitions we used for MDPs and optimal stopping. In particular, optimality of a policy means that it generates maximum possible lifetime value from every state.

We say that $\rR$ satisfies Bellman’s principle of optimality if

We can now state our main optimality result for RDPs. In the statement, $\rR$ is a well-posed RDP with value function $v^*$.

As OPI includes VFI as a special case ($m=1$), Theorem 8.1.1 also implies convergence of VFI under the stated conditions.

In terms of applications, Theorem 8.1.1 is the most important optimality result in this book. It provides the core optimality results from dynamic programming and a broadly convergent algorithm for computing optimal policies.

The proof of Theorem 8.1.1 is deferred to Section 9.1.

Example 8.1.18--Example 8.1.16 are relatively elementary. More complex models will be handled in Section 8.2.

8.1.3.4Comments on the Optimality Theorem¶

Many traditional treatments of dynamic programming build optimality theory around contractivity (see, e.g., Puterman (2005) or Stokey & Lucas (1989), Section 4.2). Assumptions are constructed so that the policy operators and Bellman operator are all contraction mappings.

While such assumptions are sufficient for Theorem 8.1.1 (since contractivity of the policy operators implies stability), they are not necessary. There are a variety of ways to prove uniqueness and stability of fixed points, including the monotonicity-based methods discussed in Section 7.1.2 and the spectral methods in Section 6.1.3.2. These alternatives will prove useful in settings where contractivity fails, as we shall see in Section 8.2.

Another point worth noting about the conditions in Theorem 8.1.1 is that no assumptions are placed on the Bellman operator. Rather, one only needs to check properties of the policy operators. This is advantageous because, unlike the Bellman operator, the policy operators do not involve maximization.

8.1.3.5Nonstationary Policies¶

Up until now, we have focused entirely on stationary policies, in the sense that the same policy is used at every point in time. What if we drop this assumption and admit the option to change policies? Might this lead to higher lifetime values?

In this section, we show that for globally stable RDPs the answer is negative. This finding justifies our focus on stationary policies.

To begin, let $\rR = (\Gamma, V, B)$ be a globally stable RDP. Recall from Remark 8.1.1 that, given $v \in V$, $\sigma \in \Sigma$, $k \in \NN$ and $x \in \Xsf$, the value $(T_\sigma^k \, v)(x)$ gives finite horizon utility over periods $0, \ldots, k$ under policy $\sigma$, with initial state $x$ and terminal condition $v$. Extending this idea, it is natural to understand $T_{\sigma_k} T_{\sigma_{k-1}} \cdots T_{\sigma_1} v$ as providing finite horizon utility values for the nonstationary policy sequence $(\sigma_k)_{k \in \NN} \subset \Sigma$, given terminal condition $v \in V$. For the same policy sequence, we define its lifetime value via

whenever the limsup is finite and independent of the terminal condition $v$.

Suppose that this is the case, and hence $\bar v$ is well defined. We claim that $\bar v \leq v^*$.

Since $\bar v$ is independent of the terminal condition $v$, we can assume without loss of generality that $v \in V_\Sigma$. By Theorem 8.1.1, we have $T^k v \to v^*$ as $k \to \infty$. Hence, by Exercise 8.11,

as was to be shown.

8.1.3.6Bounded RDPs¶

We call an RDP $\rR = (\Gamma, V, B)$ bounded if $V$ is convex and, moreover, there exist functions $v_1, v_2 \in V$ such that $v_1 \leq v_2$,

We will show that boundedness can be used to obtain optimality results for well-posed RDPs, even without global stability.

Another attractive feature of boundedness is that it permits a reduction of value space, as illustrated by the next two exercises.

Exercise 8.13 implies the reduced RDP $(\Gamma, \hat V, B)$ is also well-posed under the stated conditions, and that it contains all the $\sigma$-value functions and the value function from the original RDP $(\Gamma, V, B)$. Hence any optimality results for $(\Gamma, \hat V, B)$ carry over to $(\Gamma, V, B)$.

The next result shows that, when considering optimality, stability can be replaced by boundedness.

8.1.4Topologically Conjugate RDPs¶

Sometimes RDP models can be simplified by transformations over value space. In this section we investigate such transformations. The underlying ideas are related to topological conjugacy of dynamical systems, which we introduced in Section 2.1.1.2.

To begin, let $\rR = (\Gamma, V, B)$ and $\hat \rR = (\Gamma, \hat V, \hat B)$ be two RDPs with identical state space $\Xsf$, action space $\Asf$ and feasible correspondence $\Gamma$. We consider settings where

and, in addition, that there exists a homeomorphism $\phi$ from $\MM$ onto $\hat \MM$ such that

We call $\rR$ and $\hat R$ topologically conjugate under $\phi$ if $\phi$ is a homeomorphism $\phi$ from $\MM$ to $\hat \MM$ and (8.43) holds.

Here is our main result for this section.

The benefit of Proposition 8.1.3 is that one of these models might be easier to analyze than the other. We apply the proposition to the Epstein--Zin specification in Section 8.1.4.1 and to a smooth ambiguity model in Section 8.3.4. The next exercise will be useful for the proof.

In the next section we will see how these ideas can simplify optimality analysis.

8.1.4.1Application: Epstein--Zin RDPs¶

In this section, we show how the preceding optimality results and the notion of topologically conjugacy can be deployed to analyze the Epstein--Zin RDP from Example 8.1.7.

Recall that the aggregator in Example 8.1.7 is

Let $V = (0, \infty)^\Xsf$. We assume that $r \gg 0$ and take a nonempty feasible correspondence $\Gamma$ as given. Exercise 8.5 confirmed that $\rR \coloneq (\Gamma, V, B)$ is an RDP.

We will call the stochastic kernel $P$ irreducible if $P(x, \sigma(x), x')$ is irreducible for all $\sigma \in \Sigma$. Below we establish stability of $\rR$ under irreducibility.

To prove Proposition 8.1.4, we set up a simpler and more tractable model. Our first step is to introduce another RDP by setting

We set $\rR \coloneq (\Gamma, V, B)$ and $\hat \rR \coloneq (\Gamma, V, \hat B)$. Notice that $\hat B$ can also be expressed as

where $\theta \coloneq \gamma/\alpha$.

The value of of introducing $\hat \rR$ comes from the fact that $\hat \rR$ is easier to work with than $\rR$ (just as the modified Epstein--Zin Koopmans operator $\hat K$ defined in Section 7.2.3.3 turned out to be easier to work with than the original Epstein--Zin Koopmans operator $K$ introduced in Section 7.2.3.2).

Now we investigate the properties of the simpler RDP $\hat \rR$.

8.2Types of RDPs¶

In Section 8.1 we showed that well-posed RDPs have strong optimality properties whenever they are globally stable or bounded, and that VFI and OPI converge whenever they are globally stable. But what conditions are sufficient for these properties? We start with a relatively strict condition based on contractivity and then progress to models that fail to be contractive.

8.2.1Contracting RDPs¶

In this section, we study RDPs with strong contraction properties. Many traditional dynamic programs fit into this framework.

8.2.1.1Definition and Examples¶

Let $\rR = (\Gamma, V, B)$ be an RDP with state space $\Xsf$, action space $\Asf$, and feasible state-action pair set $\Gsf$. We call $\rR$ contracting if there exists a $\beta < 1$ such that

In line with the terminology for contraction maps, we call $\beta$ the modulus of contraction for $\rR$ when (8.49) holds.

The following corollary to Proposition 8.2.1 is immediate from Banach’s contraction mapping theorem.

8.2.1.2Error Bounds¶

Corollary 8.2.2 tells us that contracting RDPs are globally stable and, as a result, the sequence of functions in $V$ generated by VFI (Algorithm 8.2 with $m=1$) converges to $v^*$. However this result is asymptotic and conditions on $v_0 = v_\sigma$ for some $\sigma \in \Sigma$. We can improve this result in the current setting by leveraging the contraction property:

Since the VFI algorithm terminates when $\|v_k - v_{k-1} \|_{\infty}$ falls below a given tolerance, the result in (8.52) directly provides a quantitative bound on the performance of the policy returned by VFI.

8.2.1.3A Blackwell-Type Condition¶

Next we state a useful condition for contractivity that is related to Blackwell’s sufficient condition discussed in Section 2.2.3.3. We say that RDP $(\Gamma, V, B)$ satisfies Blackwell’s condition if $v \in V$ implies $v + \lambda \coloneq v + \lambda \1$ is in $V$ for every $\lambda \geq 0$ and, in addition, there exists a $\beta \in [0, 1)$ such that

8.2.1.4Application: Job Search with Quantile Preferences¶

Consider the job search problem with correlated wage draws first investigated in Section 3.3.1. With finite wage offer set $\Wsf$, wage offer process generated by $P \in \mopw$ and $\beta \in (0,1)$, we can frame this as an RDP $(\Gamma, V, B)$ with $V = \RR^\Wsf$, $\Gamma(w) = \{0, 1\}$ for $w \in \Wsf$ and

Since the model just described is an optimal stopping problem, Example 8.2.1 tells us that $(V, \Gamma, B)$ is contracting.

Now consider the following modification, where $\Gamma$ and $V$ are as before but $B$ is replaced by

where $\tau \in [0,1]$ and $R_\tau$ is the quantile certainty equivalent operator described in Exercise 7.22.

Figure Figure 8.1 shows the reservation wage for a range of $\tau$ values, computed using OPI (and taking the smallest $w \in \Wsf$ such that $\sigma^*(w) = 1$). The stationary distribution of $P$ is also shown in the figure, tilted 90 degrees.

The parameters and the code for applying $T_\sigma$ and evaluating greedy functions is shown in Listing 2. That listing includes the quantile operator $R_\tau$, which is implemented in Listing 1. (Quantiles of discrete random variables can also be computed using functionality contained in Distributions.jl.)

The main message of Figure Figure 8.1 is that the reservation wage rises in $\tau$. In essence, higher $\tau$ focuses the attention of the worker on the right tail of the distribution of continuation values. This encourages the worker to take on more risk, which leads to a higher reservation wage (i.e., reluctance to accept a given current offer).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
"Compute the τ-th quantile of v(X) when X ∼ ϕ."
function quantile(τ, v, ϕ)
    # Sort v and reorder ϕ accordingly
    indices = sortperm(v)
    v_sorted = v[indices]
    ϕ_sorted = ϕ[indices]
    
    for (i, v_value) in enumerate(v_sorted)
        p = sum(ϕ_sorted[1:i])  # sum all ϕ[j] s.t. v[j] ≤ v_value
        if p ≥ τ                # exit and return v_value if prob ≥ τ
            return v_value
        end
    end
end

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using QuantEcon
include("quantile_function.jl")

"Creates an instance of the job search model."
function create_markov_js_model(;
        n=100,       # wage grid size
        ρ=0.9,       # wage persistence
        ν=0.2,       # wage volatility
        β=0.98,      # discount factor
        c=1.0,       # unemployment compensation
        τ=0.5        # quantile parameter
    )
    mc = tauchen(n, ρ, ν)
    w_vals, P = exp.(mc.state_values), mc.p
    return (; n, w_vals, P, β, c, τ)
end

"""
The policy operator 

    (T_σ v)(w) = σ(w) (w / (1-β)) + (1 - σ(w))(c + β (R_τ v)(w))

"""
function T_σ(v, σ, model)
    (; n, w_vals, P, β, c, τ) = model
    h = c .+ β * R(τ, v, P)
    e = w_vals ./ (1 - β)
    return σ .* e + (1 .- σ) .* h
end

" Get a v-greedy policy."
function get_greedy(v, model)
    (; n, w_vals, P, β, c, τ) = model
    σ = w_vals / (1 - β) .≥ c .+ β * R(τ, v, P)
    return σ
end

8.2.1.5Application: Optimal Default¶

In this section, we consider a small open economy that borrows in international financial markets in order to smooth consumption and has the option to default. We show that the model is a contractive RDP.

Income $(Y_t)_{t \geq 0}$ is exogenous and $Q$-Markov on finite set $\Ysf$. A representative household faces budget constraint

where $C_t$ is consumption at time $t$, $q$ is the price at time $t$ of a risk-free claim on one unit of time $t+1$ consumption; $q$ is determined outside the model, say international markets; $b_t$ measures foreign lending. Purchasing a claim on $b_{t+1}$ units of time $t+1$ consumption costs $q b_{t+1}$. Purchasing bond with negative face value $b_{t+1}$ pays $q b_{t+1}$ in current consumption goods and promises to deliver $b_{t+1}$ next period.

Bond trading is managed by a benevolent government that wants to maximize household utility. Households discount future utility at rate $\beta \in (0,1)$ and current consumption $C_t$ generates current utility $u(C_t)$. The government faces borrowing constraint $b_t \geq - m$ where $m \geq 0$. The government maximizes expected discounted utility for the households.

The government can default on foreign loans. In this case, output available for consumption drops from $Y_t$ to $h(Y_t)$, where $h$ is a function satisfying $h(y) < y$ for all $y$. After a country defaults, it temporarily loses access to the international credit market.

At the end of each period during which the country is in default, it regains access to international credit markets with probability $\theta \in (0,1)$. With probability $1-\theta$ it remains in financial autarky. When a country regains access to foreign borrowing, its debt is reset to zero.

We can cast this as an RDP by considering the value of each state and action. We set the state space $\Xsf$ to be the set of all $(y, b, d)$ in $\Ysf \times \Bsf \times \{0, 1\}$, where $\Bsf$ is a finite subset of $[-m, \infty)$ indicating possible choices for bond holdings $b_t$ and $d$ is a binary variable indicating whether the country is in default ($d=0$ means not in default and $d=1$ means in default).

The value space $V$ is all of $\RR^\Xsf$. The action space is $(b_a, d_a) \in \Bsf \times \{0,1\}$ indicating choices for bond holdings and default. The feasible correspondence specifies feasible $(b_a,d_a)$ at given state $(y, b, d)$ and is given by

In other words, if $d=0$, so the country is not in default, the government can choose any $b_a \in \Bsf$ and also any $d_a \in \{0, 1\}$ (i.e., default or not default). If $d=1$, however, the government has no choices. We represent this situation by $b_a =0$ and $d_a =1$.

The value aggregator takes the form

To specify it we decompose the problem across cases for $d$ and $d_a$. First consider the case where $d=0$ (not currently in default) and $d_a=0$ (the government chooses not to default). For this case $y + b - q b_a$ is current consumption, so we set

Now consider the case where $d=0$ and $d_a=1$, so the government chooses to default. Then current consumption is $h(y)$ and we set

The term $\sum_{y'} v(y', 0, 0) Q(y, y')$ is the expected value next period when the country is readmitted to international financial markets (with $b'=0$ and $d'=0$), whereas the term $\sum_{y'} v(y', 0, 1) Q(y, y')$ is the expected value next period when default continues (with $b'=0$ and $d'=1$).

Since $B((y, b, 1), (b_a, 0), v)$ is not feasible (a defaulted country cannot itself directly choose to reenter financial markets), the only other possibility is $B((y, b, 1), (b_a, 1), v)$, which is the expected value when the country remains in default. But this is the same as $B((y, b, 0), (b_a, 1), v)$ specified earlier: The value for a country that stays in default is the same as that for a country that newly enters default.

8.2.2Eventually Contracting RDPs¶

Many RDPs are not contracting. There is no single method for handling all types of non-contractive RDPs, so we introduce alternative techniques over the next few sections. The first such technique, treated in this section, handles RDPs that contract “eventually,” even though they may fail to contract in one step. We show that these eventually contracting RDPs are globally stable, so all of the fundamental optimality results apply.

One application for these results is the MDP model with state-dependent discounting treated in Chapter 6. This section contains a proof of the main optimality result in that chapter (Proposition 6.2.2).

8.2.2.1Definition and Properties¶

Let $\rR = (\Gamma, V, B)$ be an RDP with policy set $\Sigma$. We call $\rR$ eventually contracting if there is a map $L$ from $\Gsf \times \Xsf$ to $\RR_+$ such that

for all $(x, a) \in \Gsf$ and all $v, w \in V$, and moreover,

8.2.2.2Optimality for MDPs with State-Dependent Discounting¶

With Proposition 8.2.4 in hand, we can complete the proof of Proposition 6.2.2, which pertained to optimality properties for MDPs with state-dependent discounting.

Let $(\Gamma, \beta, r, P)$ be an MDP with state-dependent discounting, as defined in Section 6.2.1.1. The state space is $\Xsf$ and the action space is $\Asf$. The function $\beta$ maps $\Gsf \times \Xsf$ to $\RR_+$. Set

for all $(x, a, x') \in \Gsf \times \Xsf$ and $\sigma \in \Sigma$.

Assume the conditions of Proposition 6.2.2, so that $\rho(L_\sigma) < 1$ for all $\sigma \in \Sigma$.

If we set

and take $V$ to be all of $\RR^\Xsf$, then $\rR \coloneq (\Gamma, V, B)$ forms an RDP, as discussed in Exercise 8.23. We claim that $\rR$ is an eventually contracting RDP.

To see this, fix $v, w \in V$ and $(x, a) \in \Gsf$. Applying the definition (8.74) and the triangle inequality, we have

Under the stated assumptions, for each $\sigma \in \Sigma$, the operator $L_\sigma(x, x') = L(x, \sigma(x), x')$ satisfies $\rho(L_\sigma) < 1$. Hence $\rR$ is eventually contracting, as claimed. Since $V = \RR^\Xsf$ is closed, Proposition 8.2.4 implies that $\rR$ is a globally stable RDP. The claims in Proposition 6.2.2 now follow from Theorem 8.1.1.

8.2.3Convex and Concave RDPs¶

Theorem 8.1.1 shows that RDPs have excellent optimality properties when all policy operators are globally stable on value space. So far we have looked at conditions for stability based on contractions (Section 8.2.1) and eventual contractions (Section 8.2.2). But sometimes both of these approaches fail and we need alternative conditions.

In this section, we explore alternative conditions based on Du’s theorem. Du’s theorem is well suited to the task of studying stability of policy operators, since it leverages the fact that all policy operators are order-preserving.

8.2.3.1Definitions and Optimality¶

Let $\rR = (\Gamma, V, B)$ be an RDP with $V = [v_1, v_2]$ for some $v_1 \leq v_2$ in $\RR^\Xsf$. We call $\rR$ convex if

1. for all $(x, a) \in \Gsf$, $\lambda \in [0, 1]$ and $v, w$ in $V$, we have

2. there exists a $\delta > 0$ such that

Analogous to the convex case, we call $\rR$ concave if

1. for all $(x, a) \in \Gsf$, $\lambda \in [0, 1]$ and $v, w$ in $V$, we have

2. there exists a $\delta > 0$ such that

In both of the these definitions, condition (ii) is rather complex. The next exercise provides simpler sufficient conditions.

Both convexity and concavity yield stability, as the next proposition shows.

It follows from Div that, for convex and concave RDPs, all of the optimality and convergence results in Theorem 8.1.1 apply.

8.2.3.2Application to MDPs¶

Div can be applied to establish optimality properties of regular MDPs. This exercise is redundant in the sense that optimality properties of regular MDPs have already been established using other means. At the same time, some of the arguments developed here will be helpful when we face more sophisticated problems.

To sketch the argument, let $\rR = (\Gamma, V, B)$ be an RDP generated by an ordinary MDP $(\Gamma, \beta, r, P)$, as discussed in Example 8.1.1. In particular, $V =\RR^\Xsf$, and $B(x,a, v) = r(x, a) + \beta \sum_{x'} v(x') P(x, a, x')$. We set $r_1 \coloneq \min r$ and $r_2 \coloneq \max r$. Then we fix $\epsilon > 0$ and define $V$ via

(The functions $v_1$ and $v_2$ are constant.) We claim that the RDP $\hat \rR \coloneq (\Gamma, \hat V, B)$ is both convex and concave.

8.3Further Applications¶

In this section, we consider some applications of the optimality results in Section 8.2.

8.3.1Risk-Sensitive RDPs¶

In Section 7.2.2 we introduced risk-sensitive preferences and discussed a recursive utility problem. Now we embed risk-sensitive preferences into a dynamic program and apply the preceding optimality results to compute optimal policies.

8.3.1.1Optimality Results¶

Consider the risk-sensitive preference RDP in Example 8.1.6, with state space $\Xsf$ and action space $\Asf$. Let $V = \RR^\Xsf$. For $(x,a) \in \Gsf$ and $v \in V$, we can express the aggregator as

where $\theta$ is a nonzero constant and

Notice that, for each fixed $a \in \Gamma(x)$, the operator $R_\theta^a$ is an entropic certainty equivalent operator on $V$ (see Example 7.3.2).

The next exercise pertains to quantile preferences rather than risk-sensitive preferences, but the result can be obtained via a relatively straightforward modification of the proof of Proposition 8.3.1.

8.3.1.2Risk-Sensitive Job Search¶

Let’s consider a job search problem where future wage outcomes are evaluated via risk-sensitive expectations. The associated Bellman operator is

Here $\theta$ is a nonzero parameter and other details are as in Section 3.3.1. We can represent the problem as an RDP with state space $\Wsf$, action space $\Asf = \{0, 1\}$, feasible correspondence $\Gamma(w) = \Asf$, value space $V \coloneq \RR^\Wsf$, and value aggregator

If $\theta < 0$, then the agent is risk-averse with respect to the gamble associated with continuing and waiting for new wage draws. If $\theta > 0$ then the agent is risk-loving with respect to such gambles. For $\theta \approx 0$, the agent is close to risk-neutral.

Figure Figure 8.2 shows how the continuation value, value function and optimal decision vary with $\theta$. Apart from $\theta$, parameters are identical to those in Listing 4. Indeed, for $\theta$ close to zero, as in the middle sub-figure of Figure Figure 8.2, we see that the value function and reservation wage are almost identical to those from the risk-neutral model in Figure Figure 3.5.

As expected, a negative value of $\theta$ tends to reduce the continuation value and hence the reservation wage, since the agent’s dislike of risk encourages early acceptance of an offer. For positive values of $\theta$ the reverse is true, as seen in the bottom sub-figure.

8.3.2Adversarial Agents¶

Some problems in economics, finance, and artificial intelligence assume that decisions emerge from a dynamic two-person zero-sum game in which the two agents’ preferences are perfectly misaligned. This can lead to a dynamic program where the Bellman equation takes the form

where $B(x, a, d, v)$ represents lifetime value for the decision maker conditional on her current action $a$ and her adversary’s action $d$. The decision maker chooses action $a \in \Gamma(x)$ with the knowledge that the opponent will then choose $d \in D(x, a)$ to minimize her lifetime value.

8.3.2.1Optimality¶

To establish optimality properties in the setting of (8.93), we introduce the following assumptions:

• If $v, w \in \RR^\Xsf$ with $v \leq w$, then

• There exists a $v_1 \in \RR^\Xsf$ and $\epsilon > 0$ such that