# Completely Abstract Dynamic Programming

John Stachurski  Research School of Economics, Australian National University
<EMAIL_ADDRESS>and  Thomas J. Sargent  Department of Economics,
New York University<EMAIL_ADDRESS>
###### Abstract.

We introduce a framework that represents dynamic programs as families of
policy operators acting on a partially ordered set. We provide an optimality
theory based on high-level assumptions and show how applications across a
broad spectrum of dynamic programming subfields fit into this framework. We
apply the framework to establish new results for specific applications.

The authors thank Dimitri Bertsekas, Anmol Bhandari, Shu Hu, Yuchao Li, Jingni
Yang, and Junnan Zhang for valuable comments and suggestions, as well as
seminar participants at the University of Minnesota, Xiamen University and
Kyoto University. Financial support from Schmidt Futures and ARC grant
FT160100423 is gratefully acknowledged.

##  1\. Introduction

Dynamic programs occur in many fields, including artificial intelligence,
biology, economics, finance, management science, and engineering (Powell et
al., (2012), Bertsekas, (2021), Kochenderfer et al., (2022)). They are used to
control aircraft, sequence of DNA, route shipping, test products, recommend
information on media platforms, and solve frontier research problems. Within
economics, applications of dynamic programming range from monetary and fiscal
policy to asset pricing, unemployment, firm investment, wealth dynamics,
inventory control, commodity pricing, sovereign default, the division of
labor, natural resource extraction, human capital accumulation, retirement
decisions, portfolio choice, and dynamic pricing.

While the conventional theory of dynamic programs—often called Markov decision
processes (MDPs)—is well understood (see, e.g., Stokey and Lucas, (1989),
Puterman, (2005), Hernández-Lerma and Lasserre, (2012), Bertsekas, (2012)),
many recent applications fall outside this framework. These include models
with Epstein–Zin preferences (Epstein and Zin,, 1989), risk-sensitive
prefereces (Jacobson,, 1973; Whittle,, 1981; Hansen and Sargent,, 1995;
Bäuerle and Jaśkiewicz,, 2018; Gao et al.,, 2021), adversarial agents (Cagetti
et al.,, 2002; Hansen and Sargent,, 2011), ambiguity (Klibanoff et al.,, 2009;
Yu et al.,, 2023), and hyperbolic discounting (Fedus et al.,, 2019).

Mathematicians have begun to build a theoretical framework that includes both
standard MDPs and the growing list of nonstandard applications discussed in
the last paragraph. Important work in this direction has been undertaken by
Bertsekas, (2022). His “abstract dynamic programming” framework, which extends
earlier ideas dating back to Denardo, (1967), Bertsekas, (1977), and
Bertsekas, (2017), starts with a generalization of a recursive statement of
optimality called the Bellman equation that exploits a temporal structure at
the heart of dynamic programming. Economic applications of the framework can
be found in Ren and Stachurski, (2021); Stachurski and Zhang, (2021); Ma and
Stachurski, (2021); Bloise et al., (2023); Toda, (2023).

Nevertheless, there remain many dynamic programs in economics, finance and
other fields that do not fit the framework of Bertsekas, (2022). For example,
because it reverses orders of expectation and maximization in a Bellman
equation, a firm valuation problem of Jovanovic, (1982) that has been built on
by many authors does not fit into this framework. A related situation arises
when we consider the “action-value” or “Q-factor” form of a Bellman equation
(see, e.g., Kochenderfer et al., (2022)), “expected value functions” and their
corresponding Bellman equations in the literature on dynamic structural
estimation (see, e.g., Rust, (1987, 1994)), the “integrated value function”
approach discussed in (Mogensen,, 2018), and the “exponential Q-factor risk-
sensitive” Bellman equations in Fei et al., (2021).

In order to capture this broader class of applications, as well as others
discussed below, the framework developed in this paper further extends the
abstract dynamic programming model constructed in Bertsekas, (2022). As a
first step, we eliminate state and action spaces. Rather than real-valued
functions on the state space, value “functions” are just points in a partially
ordered set $V$. Policies are indices over a family of “policy operators,”
written as $\\{T_{\sigma}:\sigma\in\Sigma\\}$. Each policy operator
$T_{\sigma}$ is a self-map on $V$. The lifetime value $v_{\sigma}$ of a policy
$\sigma\in\Sigma$ is identified with the unique fixed point of $T_{\sigma}$
whenever it exists. The value function $v^{*}$ is the supremum of
$\\{v_{\sigma}:\sigma\in\Sigma\\}$ and a policy $\sigma$ is defined to be
optimal when $v_{\sigma}=v^{*}$. We show that this concept of optimality
generalizes optimality concepts from the existing literature.

In this setting we provide an order-theoretic treatment of dynamic programming
and set out conditions under which the classical dynamic programming
optimality results hold (the value function is a unique fixed point of the
Bellman equation, Bellman’s principle of optimality holds, etc.), as well as
conditions under which standard algorithms converge (value function iteration,
Howard policy iteration). We begin with purely order-theoretic conditions and
then leverage these conditions in more applied settings, where the value space
$V$ has algebraic and topological structure.

In addition to extra generality, another benefit of this “completely abstract”
order-theoretic approach is that high-level abstraction isolates the role of
various assumptions and simplifies analysis. As we show, this simplicity makes
it relatively straightforward to generate new results in applied settings that
add features to existing dynamic programs, such as nonlinear certainty
equivalent operators, nonadditive aggregators, and state-dependent
discounting.

We illustrate the power of our framework via a range of applications. For
example, we show how it can be applied to problems where the order of
expectation and maximization is reversed, as in the firm valuation, Q-factor,
and structural estimation problems described above. Moreover, we show how such
problems can be further extended by adding features such as non-expected
utility preferences (Section 9.2), state-dependent discounting, unbounded
rewards, infinite-dimensional “distributional” states (Section 9.3), and so
on.

We also extend Stachurski and Zhang, (2021), Ma et al., (2020), Toda, (2019),
Toda, (2021) and Toda, (2023) by allowing for state-dependent discounting that
depends on an infinite state space (see, e.g., Section 9.3 or Section 10.2).
An advantage of this extension is that stochastic processes with well-known
properties can be used without discretization, which in turn can lead to
intuitive spectral radius conditions – similar to the conditions used for
stochastic discounting in the asset pricing literature (see, e.g., Borovička
and Stachurski, (2021)).

In Section 10.4 we show how LQ optimality results can be obtained from the
dynamic programming framework constructed in this paper. Our purpose is not to
obtain new LQ results, but rather to illustrate the generality of the
framework, since LQ results typically use relatively specialized techniques.
(For example, even the very general frameworks in Ren and Stachurski, (2021)
and Bloise et al., (2023) cannot directly accomodate LQ problems.) LQ problems
fit naturally into the order-centric methods developed in this paper, since
value functions can be identified with positive definite matrices, which can
be regarded as a partially ordered space under the Loewner order.

Regarding related literature, the more applied sections of this paper
(Sections 7 onwards) draw on recent literature on recursive utility and
dynamic programming using order-theoretic methods in function space. These
include Marinacci and Montrucchio, (2010), Marinacci and Montrucchio, (2019),
Kamihigashi, (2014), Ren and Stachurski, (2021), Balbus et al., (2014), Balbus
et al., (2018), and Becker and Rincón-Zapatero, (2021). Relative to this work
we add a new dynamic programming framework and a range of new results for
challenging single agent decision problems.

Section 2 introduces terminology and essential concepts. Section 3 introduces
“completely abstract” dynamic programs and gives examples that help illustrate
the definitions. Section 4 defines optimality and Section 5 provides
fundamental optimality results, which are then proved in Section 6. Section 7
provides more specialized optimality results, with a view to treating specific
applications. These results are proved in Section 8. Section 9 gives
applications. Section 10 extends the completely abstract framework to problems
where greedy policies do not always exist. Section 11 concludes.

##  2\. Preliminaries

Let $V=(V,\preceq)$ be a partially ordered set. Given $a,b\in V$, the set
$I=\\{v\in V:a\preceq v\preceq b\\}$ is called an order interval in $V$ and we
write $I=[a,b]$. A subset $C$ of $V$ is called a chain if it is totally
ordered by $\preceq$. A sequence $(v_{n})_{n\geqslant 1}$ in $V$ is called
ascending if $v_{n}\preceq v_{n+1}$ for all $n\in\mathbbm{N}$, and descending
if $v_{n+1}\preceq v_{n}$ for all $n\in\mathbbm{N}$. If $(v_{n})$ is ascending
(resp., descending) and $\bigvee_{n}v_{n}=v$ (resp., $\bigwedge_{n}v_{n}=v$)
for some $v\in V$, then we write $v_{n}\uparrow v$ (resp., $v_{n}\downarrow
v$).

A partially ordered set $V$ is called chain-complete (resp., countably chain-
complete) if $V$ is nonempty and every chain (resp., every empty, finite or
countable chain) in $V$ has a supremum and infimum in $V$. Every nonempty
countably chain-complete partially ordered set has a least and greatest
element (see, e.g, Davey and Priestley, (2002), Lemma 2.2).

A self-map $S$ on $V$ is called order-preserving on $V$ if $v,w\in V$ and
$v\preceq w$ implies $Sv\preceq Sw$. Let $S$ be a self-map $S$ on countably
chain-complete partially ordered set $V$ and let $\operatorname{fix}(S)$ be
all fixed points of $S$ in $V$. $S$ is called order continuous on $V$ if111Our
definition is weaker than the standard one (see, e.g., Davey and Priestley,
(2002)) but suffices for our results.

$(v_{n})\subset V\text{ and }v_{n}\uparrow v\;\implies\;Sv_{n}\uparrow Sv.$

Every order continuous self-map is also order preserving.

In our statement of the Tarski–Kantorovich fixed point theorem, $S$ is a self-
map on $V$; since our statement of the theorem is slightly nonstandard, we
include a short proof.

######  Theorem 2.1 (Tarski–Kantorovich).

If $V$ is countably chain-complete and $S$ is order continuous, then
$\operatorname{fix}(S)$ is nonempty and, in addition,

$v\in V\text{ and }v\preceq
Sv\quad\implies\quad\bigvee_{n}S^{n}v\in\operatorname{fix}(S).$

###### Proof.

Let $S,V$ be as stated and fix $v\in V$ with $v\preceq Sv$. $S$ is order
continuous and hence order-preserving, so $(v_{n})\coloneq(S^{n}v)$ is
ascending. As $V$ is countably chain-complete, the suprema
$\bigvee_{n\geqslant 1}v_{n}$ and $\bigvee_{n\geqslant 1}Sv_{n}$ exist in $V$.
If $\bar{v}\coloneq\bigvee_{n}v_{n}$, then, by order continuity,
$S\bar{v}=S\bigvee_{n\geqslant 1}v_{n}=\bigvee_{n\geqslant
1}Sv_{n}=\bigvee_{n\geqslant 2}v_{n}=\bar{v}$. Hence
$\bar{v}\in\operatorname{fix}(S)$. Since $V$ has a least element $\bot$ with
$\bot\preceq S\bot$, the set of fixed points is nonempty. ∎

We call a self-map $S$ on $V$

  * •

upward stable if $v\in V$ with $v\preceq S\,v$ and
$v^{\prime}\in\operatorname{fix}(S)$ implies $v\preceq v^{\prime}$, and

  * •

downward stable if $v\in V$ with $S\,v\preceq v$ and
$v^{\prime}\in\operatorname{fix}(S)$ implies $v^{\prime}\preceq v$.

We call $S$ order stable if $S$ is both upward and downward stable.

######  Remark 2.1.

Order stability is a weak version of stability results more typically used in
dynamic programming. For example, in the standard theory of infinite horizon
discounted dynamic programming, the Bellman operator is an order-preserving
contraction map on a complete metric space (and this result is fundamental to
the optimality proofs). We show below that while order stability weakens these
conditions (Lemma 8.1), it is still sufficient to support strong optimality
results for dynamic programs. At the same time, order stability is a purely
order-theoretic concept, permitting development of optimality theory on
abstract partially ordered sets.

In some settings, self-maps with fixed points are always order stable. The
following lemma gives one example.

######  Lemma 2.2.

Let $S$ be an order-preserving self-map on $V$. If $S$ has at most one fixed
point in $V$ and either (i) $V$ is chain-complete or (ii) $V$ is countably
chain-complete and $S$ is order continuous, then $S$ is order stable on $V$.

###### Proof.

First suppose that $V$ is chain-complete, with least element $\bot$ and
greatest element $\top$. Since $S$ is order-preserving, $S$ has fixed point
$\bar{v}\in V$ (see, e.g., Theorems 8.11 and 8.22 of Davey and Priestley,
(2002)). By assumption, $\bar{v}$ is the only fixed point of $S$ in $V$. Now
fix $v\in V$ with $v\preceq Sv$. Since $I\coloneq[v,\top]$ is itself chain-
complete, and since $S$ maps $I$ to itself, $S$ has a fixed point in $I$.
Hence $\bar{v}\in I$, which yields $v\preceq\bar{v}$. This proves upward
stability. The proof of downward stability is similar.

Now suppose that $V$ is countably chain-complete and $S$ is order continuous.
Let $\bar{v}$ be the unique fixed point of $S$ in $V$ (existence of which
follows from the Tarski–Kantorovich theorem). Pick any $v\in V$ with $v\preceq
Sv$. Since $I\coloneq[v,\top]$ is itself countably chain-complete, and since
$S$ is an order continuous map from $I$ to itself, the Tarski–Kantorovich
theorem implies that $S$ has a fixed point in $I$. Hence $\bar{v}\in I$, which
yields $v\preceq\bar{v}$. This proves upward stability. The proof of downward
stability is similar. ∎

##  3\. Abstract Dynamic Programs

In this section we introduce a high-level abstraction of a dynamic programming
problem on partially ordered sets.

###  3.1. Definition

We define an abstract dynamic program (ADP) to be a pair $(V,\mathbbm{T})$,
where

  1. (i)

$V=(V,\preceq)$ is a partially ordered set,

  2. (ii)

$\mathbbm{T}=\\{T_{\sigma}:\sigma\in\Sigma\\}$ is a family of order-preserving
self-maps on $V$, and

  3. (iii)

for each $v\in V$, the set $\\{T_{\sigma}\,v:\sigma\in\Sigma\\}$ has a
greatest element.

The set $V$ is called the value space. The operators in $\mathbbm{T}$ are
called policy operators. $\Sigma$ is an arbitrary index set and elements of
$\Sigma$ will be referred to as policies.

In applications we consider conditions under which each $T_{\sigma}$ has a
unique fixed point. In these settings, the significance of $T_{\sigma}$ is
that its fixed point represents the lifetime value (or cost) of following
policy $\sigma$. These ideas are clarified in Section 3.2.

Let $(V,\mathbbm{T})$ be an ADP with policy set $\Sigma$. Given $v\in V$, a
policy $\sigma$ in $\Sigma$ is called $v$-greedy if $T_{\sigma}\,v\succeq
T_{\tau}\,v$ for all $\tau\in\Sigma$. Condition (iii) in the definition of
ADPs states that each $v\in V$ has at least one $v$-greedy policy. We call

$Tv=\bigvee_{\sigma\in\Sigma}T_{\sigma}\,v\qquad(v\in V)$ (1)

the Bellman operator generated by $(V,\mathbbm{T})$. Evidently
$\sigma\in\Sigma$ is $v$-greedy if and only if $Tv=T_{\sigma}\,v$. Since
greedy policies exist, $T$ is a well-defined self-map on $V$. Moreover, $T$ is
order-preserving on $V$, as can be seen by fixing $v,w\in V$ with $v\preceq w$
and letting $\sigma\in\Sigma$ be $v$-greedy. Since $T_{\sigma}$ is order-
preserving, we have $Tv=T_{\sigma}\,v\preceq T_{\sigma}\,w\preceq Tw$. We say
that $v\in V$ satisfies the Bellman equation if $Tv=v$.

Below we discuss examples of ADPs. We begin with standard dynamic programs
that illustrate the model and provide concrete meaning to the objects in play.
We then introduce additional applications that do not fit existing frameworks
but nonetheless are easily framed as ADPs.

###  3.2. Example: MDPs

Markov decision processes (MDPs) are a standard framework for analyzing
dynamic programming (see, e.g., Puterman, (2005)). Consider an MDP where the
objective is to maximize

$\mathbbm{E}\sum_{t\geqslant 0}\beta^{t}r(X_{t},A_{t})$

where $X_{t}$ takes values in finite set $\mathsf{X}$ (the state space),
$A_{t}$ takes values in finite set $\mathsf{A}$ (the action space), $\Gamma$
is a nonempty correspondence from $\mathsf{X}$ to $\mathsf{A}$ (the feasible
correspondence),
$\mathsf{G}\coloneq\\{(x,a)\in\mathsf{X}\times\mathsf{A}:a\in\Gamma(x)\\}$
denotes the feasible state-action pairs, $r$ is a reward function defined on
$\mathsf{G}$, $\beta\in(0,1)$ is a discount factor, and
$P\colon\mathsf{G}\times\mathsf{X}\to[0,1]$ provides transition probabilities
and $\sum_{x^{\prime}}P(x,a,x^{\prime})=1$ .

The Bellman equation for this problem is

$v(x)=\max_{a\in\Gamma(x)}\left\\{r(x,a)+\beta\sum_{x^{\prime}}v(x^{\prime})P(x,a,x^{\prime})\right\\}\qquad\qquad(x\in\mathsf{X}).$
(2)

The set of feasible policies is the finite set
$\Sigma\coloneq\\{\sigma\in\mathsf{A}^{\mathsf{X}}:\sigma(x)\in\Gamma(x)\text{
for all }x\in\mathsf{X}\\}$. We combine $\mathbbm{R}^{\mathsf{X}}$ (the set of
all real-valued functions on $\mathsf{X}$) with the pointwise partial order
$\leqslant$ and, for $\sigma\in\Sigma$ and $v\in\mathbbm{R}^{\mathsf{X}}$,
define the MDP policy operator

$(T_{\sigma}\,v)(x)=r(x,\sigma(x))+\beta\sum_{x^{\prime}}v(x^{\prime})P(x,\sigma(x),x^{\prime})\qquad\qquad(x\in\mathsf{X}).$
(3)

Let $\mathbbm{T}=\\{T_{\sigma}:\sigma\in\Sigma\\}$. Each $T_{\sigma}$ is an
order-preserving self-map on $\mathbbm{R}^{\mathsf{X}}$. Given $v\in V$, let
$\sigma\in\Sigma$ be such that

$\sigma(x)\in\operatorname*{arg\,max}_{a\in\Gamma(x)}\left\\{r(x,a)+\beta\sum_{x^{\prime}}v(x^{\prime})P(x,a,x^{\prime})\right\\}\quad\text{for
all $x\in\mathsf{X}$}.$ (4)

(Since $\Gamma$ is nonempty, at least one such policy exists.) It is clear
that $\sigma$ satisfies $T_{\sigma}\,v\geqslant T_{\tau}\,v$ for all
$\tau\in\Sigma$, implying $\sigma$ is $v$-greedy. Hence
$(\mathbbm{R}^{\mathsf{X}},\mathbbm{T})$ is an ADP.

We stated above that, in applications, the fixed point of a given policy
operator $T_{\sigma}\in\mathbbm{T}$ is identified with the lifetime value of
policy $\sigma$. To see the idea in the MDP setting, fix $\sigma\in\Sigma$ and
let $r_{\sigma}$ and $P_{\sigma}$ be defined by

$P_{\sigma}(x,x^{\prime})\coloneq
P(x,\sigma(x),x^{\prime})\quad\text{and}\quad r_{\sigma}(x)\coloneq
r(x,\sigma(x)).$ (5)

In the present setting, the lifetime value of $\sigma$ given $X_{0}=x$ is
understood to be $v_{\sigma}(x)=\mathbbm{E}\sum_{t\geqslant
0}\beta^{t}r(X_{t},\sigma(X_{t}))$, where $(X_{t})_{t\geqslant 0}$ is a Markov
chain generated by $P_{\sigma}$ with initial condition $X_{0}=x\in\mathsf{X}$.
Pointwise on $\mathsf{X}$, we can express $v_{\sigma}$ as

$v_{\sigma}=\sum_{t\geqslant 0}(\beta P_{\sigma})^{t}r_{\sigma}=(I-\beta
P_{\sigma})^{-1}r_{\sigma}$ (6)

(see, e.g., Puterman, (2005), Theorem 6.1.1). This implies that $v_{\sigma}$
is the unique solution to the equation $v=r_{\sigma}+\beta P_{\sigma}\,v$.
From the definition of $T_{\sigma}$ in (3), this is equivalent to the
statement that $v_{\sigma}$ is the unique fixed point of $T_{\sigma}$.

Next we show that, for the ADP $(\mathbbm{R}^{\mathsf{X}},\mathbbm{T})$, the
ADP Bellman equation (1) reduces to the MDP Bellman equation (2). This
connection is important because it allows us to study optimality properties of
the MDP through optimality properties of
$(\mathbbm{R}^{\mathsf{X}},\mathbbm{T})$. To see that it holds observe that,
since $\mathbbm{R}^{\mathsf{X}}$ is endowed with the pointwise partial order,
for given $v\in V$ and $x\in\mathsf{X}$, the ADP Bellman operator (1) reduces
to

$(T\,v)(x)=\sup_{\sigma\in\Sigma}(T_{\sigma}\,v)(x)=\sup_{\sigma\in\Sigma}\left\\{r(x,\sigma(x))+\beta\sum_{x^{\prime}}v(x^{\prime})P(x,\sigma(x),x^{\prime})\right\\}.$

By the definition of $\Sigma$, we can also write this as

$(T\,v)(x)=\max_{a\in\Gamma(x)}\left\\{r(x,a)+\beta\sum_{x^{\prime}}v(x^{\prime})P(x,a,x^{\prime})\right\\}.$
(7)

It is now clear that $v$ satisfies the ADP Bellman equation $Tv=v$ if and only
if the traditional MDP Bellman equation (2) holds.

###  3.3. Example: Abstract MDPs

Next we consider an extension of the MDP framework based on the class of
dynamic programs considered in Denardo, (1967) and Bertsekas, (2022). This
extension replaces the MDP Bellman equation (2) by an abstract Bellman
equation of the form

$v(x)=\max_{a\in\Gamma(x)}B(x,a,v)\quad\text{for all }x\in\mathsf{X}.$ (8)

To simplify the exposition, we take $\mathsf{X}$, $\mathsf{A}$, $\Gamma$,
$\Sigma$ and $\mathsf{G}$ as in Section 3.2. This implies that the maximum in
(8) exists. We take $V$ to be a subset of $\mathbbm{R}^{\mathsf{X}}$ that
contains candidate value functions and assume that $B$ sends $\mathsf{G}\times
V$ into $\mathbbm{R}$. We endow $V$ with the pointwise partial order
$\leqslant$. Following Bertsekas, (2022), we assume that $B$ satisfies the
monotonicity condition

$\text{$v,w\in V$ and }v\leqslant w\implies B(x,a,v)\leqslant B(x,a,w)\;\text{
for all $(x,a)\in\mathsf{G}$}.$ (9)

We also impose the consistency condition

$v\in V\implies T_{\sigma}\,v\in V\quad\text{ when
}\quad(T_{\sigma}\,v)(x)\coloneq B(x,\sigma(x),v).$ (10)

For each $\sigma\in\Sigma$, the operator $T_{\sigma}$ is an order-preserving
self map on $V$ (as implied by (9)–(10)). For each $v\in V$, a $v$-greedy
policy can be constructed by choosing

$\sigma(x)\in\operatorname*{arg\,max}_{a\in\Gamma(x)}B(x,a,v)\quad\text{for
all $x\in X$}.$ (11)

Hence, with $\mathbbm{T}\coloneq\\{T_{\sigma}:\sigma\in\Sigma\\}$, the pair
$(V,\mathbbm{T})$ is an ADP.

In this setting, the ADP Bellman equation $Tv=v$ defined in Section 3.1
coincides with (8). Indeed, since $V$ is paired with the pointwise order,
$Tv\coloneq\bigvee_{\sigma}T_{\sigma}\,v$ becomes

$(T\,v)(x)=\sup_{\sigma\in\Sigma}\,(T_{\sigma}\,v)(x)=\max_{\sigma\in\Sigma}B(x,\sigma(x),v)=\max_{a\in\Gamma(x)}B(x,a,v).$

Hence $Tv=v$ if and only if (8) holds.

###  3.4. Example: Risk-Sensitive Q-learning

Some reinforcement learning applications use Q-factor risk-sensitive decision
processes (see, e.g., Fei et al., (2021)), where the Bellman equation has the
form

$f(x,a)=r(x,a)+\frac{\beta}{\theta}\ln\left\\{\sum_{x^{\prime}}\exp\left[\theta\max_{a^{\prime}\in\Gamma(x^{\prime})}f(x^{\prime},a^{\prime})\right]P(x,a,x^{\prime})\right\\}\qquad((x,a)\in\mathsf{G}).$
(12)

for some nonzero $\theta\in\mathbbm{R}$. (We take $\mathsf{X}$, $\mathsf{A}$,
$\Gamma$, $\Sigma$ and $\mathsf{G}$ as in our discussion of MDPs in Section
3.2.) The corresponding policy operator given policy $\sigma\in\Sigma$ is

$(T_{\sigma}f)(x,a)=r(x,a)+\frac{\beta}{\theta}\ln\left[\sum_{x^{\prime}}\exp\left[\theta
f(x^{\prime},\sigma(x^{\prime}))\right]P(x,a,x^{\prime})\right]$ (13)

where $f\in\mathbbm{R}^{\mathsf{G}}\coloneq$ all real-valued functions on
$\mathsf{G}$. With $\mathbbm{T}\coloneq\\{T_{\sigma}:\sigma\in\Sigma\\}$ and
$\mathsf{G}$ endowed with the pointwise order $\leqslant$, the pair
$(\mathbbm{R}^{\mathsf{G}},\mathbbm{T})$ is an ADP. Indeed, $T_{\sigma}$ is
order-preserving on $\mathbbm{R}^{\mathsf{G}}$ and, given
$f\in\mathbbm{R}^{\mathsf{G}}$, we can construct an $f$-greedy policy by
choosing $\sigma$ so that
$\sigma(x)\in\operatorname*{arg\,max}_{a\in\Gamma(x)}f(x,a)$ for all
$x\in\mathsf{X}$.

The ADP Bellman operator is $T\coloneq\bigvee_{\sigma}T_{\sigma}$ (see (1))
and the ADP Bellman equation is $Tf=f$. By replicating arguments in Sections
3.2–3.3, one can show that $f\in\mathsf{G}$ solves $Tf=f$ if and only if it
solves (13). This allows us to study optimality properties of the original
model (as characterized by (13)) through the ADP
$(\mathbbm{R}^{\mathsf{G}},\mathbbm{T})$.

###  3.5. Example: Structural Estimation

Rust, (1987) and many subsequent authors study discrete choice problems with
Bellman equations of the form

$g(x,a)=\int\left\\{\max_{a^{\prime}\in\mathsf{A}}\left[r(x^{\prime},a^{\prime})+\beta
g(x^{\prime},a^{\prime})\right]\right\\}P(x,a,\mathop{}\\!\mathrm{d}x^{\prime})\quad((x,a)\in\mathsf{G}\coloneq\mathsf{X}\times\mathsf{A}).$
(14)

Here $\mathsf{A}$ is a finite set, $\mathsf{X}$ is a metric space,
$r\in\mathbbm{R}^{\mathsf{G}}$ is bounded and
$P(x,a,\mathop{}\\!\mathrm{d}x^{\prime})$ is a Borel probability measure on
$\mathsf{X}$ for each $(x,a)\in\mathsf{G}$. The function $g$ is interpreted as
an “expected post-action value function.” The advantages of working with this
version of the Bellman equation are discussed in Rust, (1994), Kristensen et
al., (2021) and other sources.

We can set this problem up as an ADP by taking $\Sigma$ to be the set of Borel
measurable maps from $\mathsf{X}$ to $\mathsf{A}$ and, for each
$\sigma\in\Sigma$, introducing the policy operator

$(T_{\sigma}\,g)(x,a)=\int\left\\{r(x^{\prime},\sigma(x^{\prime}))+\beta
g(x^{\prime},\sigma(x^{\prime}))\right\\}P(x,a,\mathop{}\\!\mathrm{d}x^{\prime}).$
(15)

Under mild measurability conditions on $r$ and $P$, the operator $T_{\sigma}$
maps $b\mathsf{G}$, the set of bounded Borel measurable functions in
$\mathbbm{R}^{\mathsf{G}}$, into itself. Clearly $T_{\sigma}$ is order-
preserving on $(\mathsf{G},\leqslant)$. It is straightforward to verify any
$\sigma\in\Sigma$ obeying $\sigma(x)\in\operatorname*{arg\,max}_{a\in
A}\\{r(x,a)+\beta g(x,a)\\}$ for all $x\in\mathsf{X}$ is $g$-greedy. Hence
$(b\mathsf{G},\\{T_{\sigma}\\})$ is an ADP. Similar arguments to those given
for previous applications show that the ADP Bellman equation is equivalent to
(14).

##  4\. Properties of ADPs

In this section we define optimality for ADPs. We also categorize ADPs, with
our primary aim being to delineate properties that lead to strong optimality
results.

###  4.1. Basic Properties

Let $(V,\mathbbm{T})$ be an ADP with policy set $\Sigma$. When it exists, we
denote the unique fixed point of $T_{\sigma}$ in $V$ by $v_{\sigma}$ and call
it the $\sigma$-lifetime value function. We call $(V,\mathbbm{T})$

  * •

well-posed if each $T_{\sigma}\in\mathbbm{T}$ has a unique fixed point in $V$,

  * •

finite if $\mathbbm{T}$ is finite,

  * •

order stable if each $T_{\sigma}\in\mathbbm{T}$ is order stable on $V$, and

  * •

order continuous if each $T_{\sigma}\in\mathbbm{T}$ is order continuous on
$V$.

Finiteness, order stability and order continuity are conditions we impose when
seeking optimality results. Their significance is discussed below.

######  Example 4.1.

The ADP $(\mathbbm{R}^{\mathsf{X}},\mathbbm{T})$ generated by the MDP model in
Section 3.2 is finite, well-posed, and order stable. Finiteness holds because
$\mathsf{X}$ and $\mathsf{A}$ are finite.
$(\mathbbm{R}^{\mathsf{X}},\mathbbm{T})$ is well-posed because, under the
stated assumptions, $T_{\sigma}\,v=r_{\sigma}+\beta P_{\sigma}\,v$ has a
unique fixed point in $\mathbbm{R}^{\mathsf{X}}$ given by
$v_{\sigma}\coloneq(I-\beta P_{\sigma})^{-1}r_{\sigma}$. $T$ is upward stable
because, given $v\in\mathbbm{R}^{\mathsf{X}}$ with $v\leqslant T\,v$, we have
$(I-\beta P_{\sigma})v\leqslant r_{\sigma}$ and, since $(I-\beta
P_{\sigma})^{-1}=\sum_{t=1}^{\infty}(\beta P_{\sigma})^{t}$ is nonnegative,
$v\leqslant(I-\beta P_{\sigma})^{-1}r_{\sigma}=v_{\sigma}$. Reversing the
inequalities shows that downward stability holds.

We consider applications in which the lifetime value of a policy $\sigma$
coincides with the fixed point $v_{\sigma}$ of its policy operator
$T_{\sigma}$. Well-posedness is a minimal condition because without it we
cannot be sure that policies have well-defined lifetime values. Maximizing
lifetime values (or, equivalently, minimizing lifetime costs) is the objective
of dynamic programming.

Below we use order stability as a condition for optimality. At least in simple
settings, it is a weak condition. For example, Lemma 2.2 implies that if
$(V,\mathbbm{T})$ is a well-posed ADP and $V$ is chain complete, then
$(V,\mathbbm{T})$ is order stable.

###  4.2. Defining Optimality

Next we define optimality for ADPs using concepts that are direct
generalizations of dynamic program optimality from in existing frameworks. To
begin, for a well-posed ADP $(V,\mathbbm{T})$ with policy set $\Sigma$, we set

$V_{\Sigma}\coloneq\\{v_{\sigma}:\sigma\in\Sigma\\}=\text{ the set of lifetime
value functions generated by $(V,\mathbbm{T})$}.$

A policy $\sigma\in\Sigma$ is called optimal for $(V,\mathbbm{T})$ if
$v_{\sigma}$ is a greatest element of $V_{\Sigma}$.

######  Example 4.2.

The ADP $(\mathbbm{R}^{\mathsf{X}},\mathbbm{T})$ generated by the MDP model in
Section 3.2 uses the pointwise partial order on $\mathbbm{R}^{\mathsf{X}}$, so
$v_{\sigma}$ is optimal if and only if
$v_{\sigma}(x)=\max_{\tau\in\Sigma}v_{\tau}(x)$ for all $x\in\mathsf{X}$. This
is the standard definition of optimality of MDP policies (see, e.g., Puterman,
(2005), Ch. 6).

We say that Bellman’s principle of optimality holds if $V_{\Sigma}$ has a
greatest element $v^{*}$ and, for $\sigma\in\Sigma$,

$\text{$\sigma$ is optimal }\iff\text{ $\sigma$ is $v^{*}$-greedy}.$

######  Example 4.3.

The ADP generated by the MDP model in Section 3.2 satisfies Bellman’s
principle of optimality. See, for example, Bertsekas, (2022), Lemma 2.1.1 (c).

We say that the fundamental Bellman optimality results hold for
$(V,\mathbbm{T})$ if

  1. (B1)

$V_{\Sigma}$ has a greatest element $v^{*}$,

  2. (B2)

$v^{*}$ is the unique solution to the Bellman equation in $V$, and

  3. (B3)

Bellman’s principle of optimality holds.

When (B1) holds we call the greatest element $v^{*}$ the value function.
Clearly (B1) is equivalent to the statement that at least one optimal policy
exists.

######  Remark 4.1.

Properties (B1)–(B3) are not independent. In particular, (B1)–(B2) imply (B3).
To see this, assume (B1)–(B2) and recall that $\sigma$ is optimal if and only
if $v_{\sigma}=v^{*}$. Since $v_{\sigma}$ is the unique fixed point of
$T_{\sigma}$, this is equivalent to $T_{\sigma}\,v^{*}=v^{*}$. Since
$T\,v^{*}=v^{*}$, the last statement is equivalent to
$T_{\sigma}\,v^{*}=Tv^{*}$, which is in turn equivalent to the statement that
$\sigma$ is $v^{*}$-greedy. Hence Bellman’s principle of optimality holds.

######  Remark 4.2.

Puterman, (2005) shows that, for MDPs, $\sigma$ is optimal if and only if
$Tv_{\sigma}=v_{\sigma}$, where $T$ is the MDP Bellman operator and
$v_{\sigma}$ is lifetime value of policy $\sigma$ (Theorem 6.2.6). This result
extends to any well-posed ADP $(V,\mathbbm{T})$. Indeed, if (B1)–(B2) hold,
then $\operatorname{fix}(T)=\\{v^{*}\\}$, so $Tv_{\sigma}=v_{\sigma}$ if and
only if $v_{\sigma}=v^{*}$. Since $v^{*}$ is the greatest element of
$V_{\Sigma}$, this is equivalent to optimality.

###  4.3. Algorithms

Let $(V,\mathbbm{T})$ be a well-posed ADP with Bellman operator $T$ and
$\sigma$-lifetime value functions $V_{\Sigma}$. Suppose that the fundamental
optimality properties (B1)–(B3) hold and let $v^{*}$ denote the value
function. We consider algorithms for computing $v^{*}$. (An optimal policy can
then be computed using Bellman’s principle of optimality.) Here an below,

$V_{u}\coloneq\\{\text{ all $v\in V$ with $v\preceq Tv$ }\\}.$

Note that $V_{\Sigma}\subset V_{u}$ because, for $v_{\sigma}\in V_{\Sigma}$,
we have $v_{\sigma}=T_{\sigma}\,v_{\sigma}\preceq Tv_{\sigma}$.

We consider two major algorithms, value function iteration and Howard policy
iteration. We say that value function iteration converges if, for all $v\in
V_{u}$, we have $T^{n}v\uparrow v^{*}$. (The sequence $(T^{n}v)$ is ascending
because $T$ is order-preserving.) We define the Howard policy operator
$H\colon V\to V_{\Sigma}$ corresponding to $(V,\mathbbm{T})$ via

$Hv=v_{\sigma}\quad\text{ where $\sigma$ is $v$-greedy}.$

So that $H$ is well-defined, we always select the same $v$-greedy policy when
applying $H$ to $v$.222Formally, selecting a designated $v$-greedy policy
requires the Axiom of Choice. However, most applications admit simpler
selection mechanisms. Iterating with $H$ is an abstraction of Howard policy
iteration. We say that Howard policy iteration converges if $V_{\Sigma}$ has a
greatest element $v^{*}$ and, for all $v\in V$, we have $H^{n}v\uparrow
v^{*}$. We say that Howard policy iteration converges in finitely many steps
if, in addition, there exists a $k\in\mathbbm{N}$ with $H^{n}v=v^{*}$.

##  5\. Optimality on Partially Ordered Sets

Our first set of optimality results assume that $V$ is a partially order set
without any algebraic or topological structure. _Throughout this section,
$(V,\mathbbm{T})$ is a well-posed ADP_. Proofs are deferred to Section 6.

First, we state a high-level result that assumes the existence of a fixed
point for the Bellman operator. Below we use this theorem as an intermediate
result.

######  Theorem 5.1.

If $(V,\mathbbm{T})$ is downward stable and $T$ has at least one fixed point
in $V$, then the fundamental Bellman optimal results hold.

Now we drop the assumption that $T$ has a fixed point and suppose instead that
$V$ has some form of completeness. We begin with a relatively strong
completeness assumption. The result shows that every well-posed ADP has strong
optimality properties in this setting.

######  Theorem 5.2.

If the value space $V$ is chain-complete, then the fundamental Bellman optimal
results hold.

The next result weakens chain-completeness to a milder condition on the space,
while adding continuity properties on the policy operators.

######  Theorem 5.3.

If $(V,\mathbbm{T})$ is order continuous and $V$ is countably chain-complete,
then the fundamental Bellman optimal results hold. Moreover, value function
iteration and Howard policy iteration both converge.

Comparing Theorem 5.3 with Theorem 5.2, we find that the slightly modified
assumptions on the value space and policy operators deliver not only the same
optimality results but also useful convergence results.

Finally, we state a result for the case where $(V,\mathbbm{T})$ is finite,
which is relatively common in applications.

######  Theorem 5.4.

If $(V,\mathbbm{T})$ is finite and order stable, then the fundamental Bellman
optimal results hold. In addition, Howard policy iteration converges to the
value function $v^{*}$ in finitely many steps.

The proofs of Theorems 5.1–5.2 are provided in Section 6.

##  6\. Proofs of Section 5 Results

In this section we prove optimality results from Section 5. We begin with a
lemma that collects some useful results for well-posed ADPs. In the lemma,
$(V,\mathbbm{T})$ is an ADP with Howard policy operator $H$ and Bellman
operator $T$.

######  Lemma 6.1.

If $(V,\mathbbm{T})$ is well-posed and $v\in V$, then the following statements
hold:

  1. (L1)

If $Hv=v$, then $Tv=v$.

  2. (L2)

If $(V,\mathbbm{T})$ is downward stable and $Tv=v$, then $v$ is a greatest
element of $V_{\Sigma}$.

  3. (L3)

If $(V,\mathbbm{T})$ is upward stable, $n\in\mathbbm{N}$, and $v_{n}=H^{n}v$,
then $v_{n}\preceq Tv_{n}\preceq v_{n+1}$.

###### Proof.

Regarding (L1), fix $v\in V$ with $H\,v=v$ and let $\sigma$ be a $v$-greedy
policy such that $H\,v=v_{\sigma}$. Then $v_{\sigma}=v$, and, since $\sigma$
is $v$-greedy, $T_{\sigma}\,v=T\,v$. Since $v_{\sigma}$ is fixed for
$T_{\sigma}$, we have $Tv=T_{\sigma}\,v=T_{\sigma}\,v_{\sigma}=v_{\sigma}=v$.

Regarding (L2), let $v$ be a fixed point of $T$ in $V$. Existence of greedy
policies implies that there exists a $\sigma\in\Sigma$ such that
$v=T\,v=T_{\sigma}\,v$. But $T_{\sigma}$ has a unique fixed point in $V$,
equal to $v_{\sigma}$, so $v=v_{\sigma}$. Moreover, if $\tau$ is any policy,
then $T_{\tau}\,v\preceq T\,v=v$ and hence, by downward stability,
$v_{\tau}\preceq v$. These facts imply that $v$ is a greatest element of
$V_{\Sigma}$.

Regarding (L3), let $v_{n}$ be as stated and let $w_{n}=Tv_{n}$ for all
$n\in\mathbbm{N}$. Fixing $n\in\mathbbm{N}$ we have $v_{n}\in
V_{\Sigma}\subset V_{u}$, so $v_{n}\preceq w_{n}$. It remains to show that
$w_{n}\preceq v_{n+1}$. To this end, choose $\sigma\in\Sigma$ such that
$\sigma$ is $v_{n}$-greedy and $v_{\sigma}=v_{n+1}$. For this choice of
$\sigma$, we have $w_{n}=Tv_{n}=T_{\sigma}\,v_{n}\preceq
T_{\sigma}Tv_{n}=T_{\sigma}\,w_{n}$, where the inequality follows from the
fact that $T_{\sigma}$ is order-preserving and $v_{n}\in V_{u}$. We have just
shown that $w_{n}\preceq T_{\sigma}\,w_{n}$, and hence, by upward stability,
$w_{n}\preceq v_{\sigma}=v_{n+1}$. ∎

######  Lemma 6.2.

If $(V,\mathbbm{T})$ is order continuous and $V$ is countably chain-complete,
then $T$ is order continuous on $V$.

###### Proof.

Fix $(v_{n})\subset V$ with $v_{n}\uparrow\bar{v}\in V$. Since, $T$ is order-
preserving, $(Tv_{n})_{n\geqslant 1}$ is also ascending. Hence
$\bigvee_{n}Tv_{n}$ exists in $V$. We claim that $\bigvee_{n}Tv_{n}=T\bar{v}$.

On one hand, $T\bar{v}$ is an upper bound for $(Tv_{n})$. On the other hand,
if $w\in V$ is such that $Tv_{n}\preceq w$ for all $n$, then
$T_{\sigma}\,v_{n}\preceq w$ for all $n$ and $\sigma$. Fixing
$\sigma\in\Sigma$, taking the supremum over $n$ and using order-continuity of
$T_{\sigma}$ gives $T_{\sigma}\,\bar{v}\preceq w$. Hence $T\bar{v}\preceq w$,
which means that $T\bar{v}$ is a least upper bound of $(Tv_{n})$. This
confirms that $\bigvee_{n}Tv_{n}=T\bar{v}$. Hence $T$ is order continuous. ∎

We now prove the main optimality results from Section 5. In proving the
Bellman optimality properties (B1)–(B3), we apply Remark 4.1, which tells us
that (B1)–(B2) are sufficient. For the remainder of this section,
$(V,\mathbbm{T})$ is a well-posed ADP with policy operators
$\mathbbm{T}=\\{T_{\sigma}\\}_{\sigma\in\Sigma}$, Bellman operator $T$ and
Howard policy operator $H$.

###### Proof of Theorem 5.1.

Let $(V,\mathbbm{T})$ be downward stable and suppose that $T$ has at least one
fixed point $v$ in $V$. By Lemma 6.1 (L2), $v$ is the greatest element of
$V_{\Sigma}$ and the unique solution to the Bellman equation in $V$. These
facts suffice for the fundamental Bellman optimality properties to hold. ∎

###### Proof of Theorem 5.2.

Let $V$ be chain-complete. $(V,\mathbbm{T})$ is order stable by Lemma 2.2 and
$T$ has at least one fixed point in $V$ (see, e.g., Theorems 8.11 and 8.22 of
Davey and Priestley, (2002)). Hence the conditions of Theorem 5.1 hold, which
implies the fundamental Bellman optimality properties. ∎

###### Proof of Theorem 5.3.

Suppose $(V,\mathbbm{T})$ is order continuous and $V$ is countably chain-
complete. By Lemma 2.2, $(V,\mathbbm{T})$ is order stable. Fix $v\in V$ and
set $v_{n}=H^{n}v$ and $w_{n}=Tv_{n}$ for all $n\in\mathbbm{N}$. By Lemma 6.1
(L3), the sequences $(v_{n})$ and $(w_{n})$ are ascending with $v_{n}\preceq
w_{n}\preceq v_{n+1}$ for all $n\in\mathbbm{N}$. Setting
$\bar{v}=\bigvee_{n}v_{n}$, we obtain
$\bar{v}=\bigvee_{n}v_{n}\preceq\bigvee_{n}w_{n}\preceq\bigvee_{n}v_{n+1}=\bar{v}$.
In particular, $\bigvee_{n}w_{n}=\bar{v}$. Using the fact that $T$ is order
continuous on $V$ (Lemma 6.2), we obtain
$T\bar{v}=T\bigvee_{n}v_{n}=\bigvee_{n}Tv_{n}=\bigvee_{n}w_{n}=\bar{v}$. Hence
$\bar{v}$ is a fixed point of $T$ in $V$. It now follows from Theorem 5.1 that
the fundamental optimality properties hold. Moreover,
$\bigvee_{n}H^{n}v=\bar{v}=v^{*}$, so Howard policy iteration converges.
Finally, for $v\in V_{u}$ the sequence $v_{n}\coloneq T^{n}v$ is ascending.
Since $T$ is order continuous, the supremum is a fixed point of $T$ (Theorem
2.1). By Lemma 6.1 (L2), the fixed point is $v^{*}$, so value function
iteration converges. ∎

###### Proof of Theorem 5.4.

Let $(V,\mathbbm{T})$ be order stable and finite. Fix $v\in V$ and let
$v_{n}=H^{n}v$ for all $n\in\mathbbm{N}$. By Lemma 6.1 (L3), $v_{n}\preceq
v_{n+1}$ for all $n\in\mathbbm{N}$. Since $(v_{n})$ is contained in the finite
set $V_{\Sigma}$, it must be that $v_{n+1}=v_{n}$ for some $n\in\mathbbm{N}$.
But then $H\,v_{n}=v_{n}$, so, by Lemma 6.1 (L1)–(L2), we have $v_{n}=v^{*}$
and, moreover, $v^{*}$ is the unique solution to the Bellman equation in $V$.
(Uniqueness is by (L2) and the fact that greatest elements are unique.) This
implies that the fundamental Bellman optimality properties hold. We have also
shown that Howard policy iteration converges in finitely many steps. ∎

##  7\. Further Optimality Results

In Section 5 we obtained relatively high level optimality results for ADPs
defined on partially ordered sets. Next we generate more applicable results by
adding structure to the ADPs we consider. Since there are many kinds of
dynamic programs, we consider a range of sufficient conditions. Proofs are
deferred to Section 8.

###  7.1. ADPs in Ordered Vector Space

Let $E=(E,\leqslant)$ be an ordered vector space (see., e.g., Zaanen, (2012))
with zero element $0$. $E$ is called countably Dedekind complete if every
finite or countable subset of $E$ that is bounded above (resp., bounded below)
has a supremum (resp., infimum). The positive cone $E_{+}$ of $E$ is all $v\in
E$ with $v\geqslant 0$. For $v,v^{\prime}\in E$ we write $v<v^{\prime}$ if
$v\leqslant v^{\prime}$ and $v$ and $v^{\prime}$ are distinct.

Following Marinacci and Montrucchio, (2019), we define the lower perimeter of
$A\subset E$ as

$\partial A\coloneq\\{v\in A:\exists\,v^{\prime}\in A\ \mathrm{s.t.}\
v<v^{\prime}\text{ and }tv+(1-t)v^{\prime}\notin A\text{ whenever }t>1\\}.$

Thus, $v\in\partial A$ if $v$ is dominated by some $v^{\prime}\in A$ and,
moreover, the line segment that joins $v$ and $v^{\prime}$ cannot be extended
beyond $v$ without exiting $A$.

Let $V$ be a nonempty order interval in $E$. An operator $S\colon V\to V$ is
called order concave if, given any $v,v^{\prime}\in V$ with $v\leqslant
v^{\prime}$,

$S(tv+(1-t)v^{\prime})\geqslant tSv+(1-t)Sv^{\prime}\quad\text{for all
}t\in[0,1].$

Let $(V,\mathbbm{T})$ be an ADP. We call $(V,\mathbbm{T})$ concave if $V$ is
an order interval in $E$, every $T_{\sigma}\in\mathbbm{T}$ is order concave on
$V$ and, in addition, $T_{\sigma}\,v>v$ whenever $v\in\partial V$.

######  Theorem 7.1.

Let $V$ be an order interval in a countably Dedekind complete ordered vector
space $E$ and let $(V,\mathbbm{T})$ be an ADP. If $(V,\mathbbm{T})$ is concave
and order continuous, then

  1. (i)

$(V,\mathbbm{T})$ is well-posed,

  2. (ii)

the fundamental Bellman optimality properties hold, and

  3. (iii)

Howard policy iteration and value function iteration both converge.

###  7.2. ADPs in Riesz Space

We now add some additional structure by assuming that $E$ is a Riesz space
(i.e., an ordered vector space that is also a lattice; see Zaanen, (2012) for
definitions). The benefit of this extra structure is that it allows us to use
contraction-like conditions via absolute values (even when no metric structure
exists).

The absolute value of $v\in E$ is denoted by $|v|$. A sequence $(v_{n})\subset
E$ is said to order converge to $v\in E$, and we write
$v_{n}\stackrel{{\scriptstyle o}}{{\to}}v$, if there exists a descending
sequence $(d_{n})\subset E$ such that $|v_{n}-v|\leqslant d_{n}$ for all $n$
and $d_{n}\downarrow 0$.

Let $E$ be a Riesz space and let $(V,\mathbbm{T})$ be an ADP where $V$ is a
subset of $E$. We call $(V,\mathbbm{T})$ eventually order contracting if, for
each $\sigma\in\Sigma$, there exists an order continuous self-map $K_{\sigma}$
on $E_{+}$ such that

  1. (R1)

$v_{n}\downarrow v$ implies $K_{\sigma}\,v_{n}\downarrow K_{\sigma}\,v$,

  2. (R2)

$K_{\sigma}^{n}\,v\stackrel{{\scriptstyle o}}{{\to}}0$ for all $v\in E_{+}$,
and, for all $v,w\in V$,

$|T_{\sigma}\,v-T_{\sigma}\,w|\leqslant K_{\sigma}|v-w|.$ (16)

Conditions (R1)–(R2) generalize contraction mapping conditions often used for
dynamic programming in discounted environments (see, e.g., Puterman, (2005),
Bertsekas, (2022) or Stokey and Lucas, (1989)). The benefits of (R1)–(R2) are:
(a) the rate of convergence to zero can be arbitrarily slow, (b) the rate can
depend on the policy, and (c) the space $V$ need not have any norm or
metric.333Condition (R1) is similar to order continuity, and equivalent to
order continuity when $K_{\sigma}$ is a linear operator.

######  Theorem 7.2.

Let $V$ be an order interval in a countably Dedekind complete Riesz space $E$
and let $(V,\mathbbm{T})$ be an ADP. If $(V,\mathbbm{T})$ is eventually order
contracting, then

  1. (i)

$(V,\mathbbm{T})$ is well-posed,

  2. (ii)

the fundamental Bellman optimality properties hold, and

  3. (iii)

Howard policy iteration and value function iteration both converge.

###  7.3. ADPs in Partially Ordered Space

Our next result combines topology and order (unlike Sections 7.1–7.2, which
combined algebraic structure and order). The setting we work in is a partially
ordered space, which is a metric space $V=(V,d)$ with partial order $\preceq$
that is preserved under limits: $d(v_{n},v)\to 0$ and $d(u_{n},u)\to 0$ with
$u_{n}\preceq v_{n}$ for all $n$ implies $u\preceq v$. We call a self-map $S$
on $V$ globally stable on $V$ if $S$ has a unique fixed point $\bar{v}$ in $V$
and $d(S^{n}v,\bar{v})\to 0$ as $n\to\infty$ for all $v\in V$.

######  Theorem 7.3.

Let $(V,\mathbbm{T})$ be an ADP with Bellman operator $T$. If $V$ is a
partially ordered space and $T$ and each $T_{\sigma}\in\mathbbm{T}$ are
globally stable, then

  1. (i)

$(V,\mathbbm{T})$ is well-posed,

  2. (ii)

the fundamental Bellman optimality properties hold, and

  3. (iii)

Howard policy iteration and value function iteration both converge.

Some standard results are special cases of Theorem 7.3, such as when policy
and Bellman operators are all contraction mappings on a suitable function
space.

###  7.4. ADPs on a Banach Lattice

Sections 7.1–7.2 treated ADPs in settings where the value space has order and
algebraic structure. Section 7.3 treated ADPs in settings with order and
topological structure (partially ordered spaces). Here we combine these
features (order, algebraic operations and topology) by studying ADPs where the
value space is a subset of a Banach lattice.

As usual, a Banach lattice $E=(E,\leqslant,\|\cdot\|)$ is a Riesz space paired
with a lattice norm $\|\cdot\|$ such that $(E,\|\cdot\|)$ is complete. Under
the metric induced by the norm, every subset of a Banach lattice is a
partially ordered space.

Let $(V,\mathbbm{T})$ be an ADP where $V$ is a subset of a Banach lattice $E$
and $v+h\in V$ whenever $v\in V$ and $h\in E_{+}$. In this setting, We call
$(V,\mathbbm{T})$ eventually Blackwell contracting if there exists an order-
preserving self-map $K$ on $E_{+}$ such that

  1. (E1)

$\exists\;\lambda,M\in\mathbbm{R}_{+}$ with $\lambda<1$ and
$\|K^{n}u\|\leqslant M\lambda^{n}\|u\|$ for all $n\in\mathbbm{N}$ and $u\in
E_{+}$, and

  2. (E2)

$T_{\sigma}(v+h)\leqslant T_{\sigma}\,v+Kh$ for all
$T_{\sigma}\in\mathbbm{T}$, $v\in V$ and $h\in E_{+}$.

This condition generalizes a Blackwell condition for optimality that is
popular in the literature on dynamic programming (see, e.g., Stokey and Lucas,
(1989), Theorem 3.3).

We can now state our main result for ADPs on Banach lattices.

######  Theorem 7.4.

Let $E$ be a Banach lattice and let $(V,\mathbbm{T})$ be an ADP where $V$ is a
closed subset of $E$ obeying $v+h\in V$ whenever $v\in V$ and $h\in E_{+}$. If
$(V,\mathbbm{T})$ is eventually Blackwell contracting, then

  1. (i)

$(V,\mathbbm{T})$ is well-posed,

  2. (ii)

the fundamental Bellman optimality properties hold, and

  3. (iii)

Howard policy iteration and value function iteration both converge.

Theorem 7.4 is related to Theorem 7.2, in the sense that both conditions
produce eventual contractions (see the proofs in Section 8. At the same time,
Theorem 7.4 adds value because it does not require any form of Dedekind
completeness. The proof of Theorem 7.4 uses Theorem 7.3.

##  8\. Proofs of Section 7 Results

In this section we prove all results from Section 7. For the proof we note
that, in the Riesz space setting, if $(v_{n})\subset E$ is ascending, then
$v_{n}\uparrow v$ if and only if $v_{n}\stackrel{{\scriptstyle o}}{{\to}}v$.

###### Proof of Theorem 7.1.

Let $(V,\mathbbm{T})$ be as stated, with $V$ an order interval in a countably
Dedekind complete ordered vector space. Since $(V,\mathbbm{T})$ is order
continuous and $V$ is countably chain complete, Theorem 5.3 implies all claims
in Theorem 7.1 hold when $(V,\mathbbm{T})$ is well-posed. To see that this is
so, fix $\sigma\in\Sigma$. Since $V$ is countably chain complete, $T_{\sigma}$
is an order concave and order continuous self-map on $V$ and, moreover,
$T_{\sigma}\,v\notin\partial V$ whenever $v\in\partial V$, Theorem 1 of
Marinacci and Montrucchio, (2019) implies that $T_{\sigma}$ has a unique fixed
point in $V$. Hence $(V,\mathbbm{T})$ is well-posed. ∎

###### Proof of Theorem 7.2.

Let $(V,\mathbbm{T})$ and $E$ be as stated. Since $V$ is an order interval in
a countably Dedekind complete Riesz space, $V$ is countably chain complete.
Hence, by Theorem 5.3, we need only show that $(V,\mathbbm{T})$ is well-posed
and order continuous.

Regarding order continuity, fix $T_{\sigma}\in\mathbbm{T}$ and $(v_{n})\subset
V$ with $v_{n}\uparrow v\in V$. We claim that $T_{\sigma}\,v_{n}\uparrow
T_{\sigma}\,v$. Since $(T_{\sigma}\,v_{n})$ is ascending, it suffices to show
that $T_{\sigma}\,v_{n}\stackrel{{\scriptstyle o}}{{\to}}T_{\sigma}\,v$.
Applying (16) gives $|T_{\sigma}\,v_{n}-T_{\sigma}\,v|\leqslant
K_{\sigma}|v_{n}-v|$. Since $v_{n}\uparrow v$, we have
$|v_{n}-v|=v-v_{n}\downarrow 0$. Applying (R1) now yields
$K_{\sigma}|v_{n}-v|\downarrow 0$. Hence
$T_{\sigma}\,v_{n}\stackrel{{\scriptstyle o}}{{\to}}T_{\sigma}\,v$ and order
continuity is confirmed.

Regarding well-posedness, fix $T_{\sigma}\in\mathbbm{T}$ and observe that
$T_{\sigma}$ is order-preserving on the countably chain complete set $V$.
Hence, by the Tarski–Kantorovich theorem, $T_{\sigma}$ has at least one fixed
point $v\in V$. To prove uniqueness, we take $w$ to be any other fixed point
of $T_{\sigma}$ in $V$. Iterating on (16) and using (R1), which implies that
$K_{\sigma}$ is order-preserving on $E$, we get
$|v-w|=|T_{\sigma}^{n}\,v-T_{\sigma}^{n}\,w|\leqslant K_{\sigma}^{n}|v-w|$.
Since $K_{\sigma}$ is order contracting, there exists a sequence $(d_{n})$
with $d_{n}\downarrow 0$ and $K_{\sigma}^{n}|v-w|\leqslant d_{n}$ for all $n$.
Taking the infimum gives $|v-w|=0$. Hence $v=w$. ∎

To prove Theorem 7.3 we first establish the following lemma.

######  Lemma 8.1.

If $V$ is a partially ordered space and $S$ is order-preserving and globally
stable on $V$, then $S$ is order stable on $V$.

###### Proof.

Let $S$ have the stated properties and let $\bar{v}$ be the unique fixed point
of $S$ in $V$. Upward stability holds because if $v\in V$ and $v\preceq S\,v$,
then, iterating on this inequality and using the fact that $S$ is order-
preserving, we have $v\preceq S^{n}v$ for all $n\in\mathbbm{N}$. Taking the
limit gives $v\preceq\bar{v}$. Hence upward stability holds. The proof of
downward stability is similar. ∎

In the proof of Theorem 7.3, we use the fact that if $(v_{n})$ is an ascending
sequence in $V$ and $d(v_{n},v)\to 0$ for some $v\in V$, then $v_{n}\uparrow
v$. (This holds because $v$ is an upper bound of $(v_{n})$ and, if $w$ is any
upper bound, then $v_{n}\preceq w$ for all $n$, so $v\preceq w$.)

###### Proof of Theorem 7.3.

Assume the conditions of the theorem. Lemma 8.1 and the global stability of
each $T_{\sigma}\in\mathbbm{T}$ imply that $(V,\mathbbm{T})$ is order stable.
Also, $T$ is globally stable and hence has a fixed point in $V$. Theorem 5.1
now implies that the fundamental Bellman optimality properties hold.

Regarding convergence of value function iteration, fix $v\in V_{u}$. The
sequence $(v_{n})\coloneq(T^{n}v)$ is ascending and, by global stability,
$d(v_{n},v^{*})\to 0$. Hence $T^{n}v\uparrow v^{*}$.

Regarding convergence of Howard policy iteration, fix $v\in V$ and let
$v_{n}=H^{n}v$ for all $n$. By Lemma 6.1 (L3), we have $v_{n}\preceq
Tv_{n}\preceq v_{n+1}$ for all $n\geqslant 1$. Iterating on this chain of
inequalities and using the fact that $T$ is order-preserving gives
$T^{n}v_{1}\preceq v_{n+1}$ for all $n$. By global stability,
$d(T^{n}v_{1},v^{*})\to 0$. In addition, the sequence $(T^{n}v_{1})$ is
ascending because $v_{1}\in V_{\Sigma}\subset V_{u}$. Hence
$T^{n}v_{1}\uparrow v^{*}$. Since $T^{n}v_{1}\preceq v_{n+1}$ for all $n$,
this yields $v_{n}\uparrow v^{*}$. ∎

Next we prove Theorem 7.4. We will use the fact that, in a Banach lattice,
$(v_{n})\subset E$ ascending (resp., descending) and $\|v_{n}-v\|\to 0$
implies $v_{n}\uparrow v$ (resp., $v_{n}\downarrow v$). See, for example,
Zaanen, (2012), Theorem 15.3. We begin with the following lemma.

######  Lemma 8.2.

Let $V$ be a closed subset of a Banach lattice $E$ obeying $v+h\in V$ whenever
$v\in V$ and $h\in E_{+}$. If $(V,\mathbbm{T})$ is an eventually Blackwell
contracting ADP, then

$|T_{\sigma}\,v-T_{\sigma}\,w|\leqslant K|v-w|\quad\text{for all
$T_{\sigma}\in\mathbbm{T}$ and $v,w\in V$}.$ (17)

In addition, (17) implies that all $T_{\sigma}\in\mathbbm{T}$ and
$T\coloneq\bigvee_{\sigma}T_{\sigma}$ are globally stable on $V$.

###### Proof.

Let the stated properties hold and fix $T_{\sigma}\in\mathbbm{T}$ and $v,w\in
V$. Since $T_{\sigma}$ is order-preserving and (E2) on page 7.4 holds, we have

$T_{\sigma}\,v=T_{\sigma}(w+v-w)\leqslant T_{\sigma}(w+|v-w|)\leqslant
T_{\sigma}\,w+K|v-w|.$

Rearranging gives $T_{\sigma}\,v-T_{\sigma}\,w\leqslant K|v-w|$. Reversing the
roles of $v$ and $w$ proves (17).

Regarding the second claim in the lemma, we again fix
$T_{\sigma}\in\mathbbm{T}$, $v,w\in V$, and $n\in\mathbbm{N}$. Let $\|\cdot\|$
be the norm on $E$. By (17) we have
$|T_{\sigma}^{n}v-T_{\sigma}^{n}w|\leqslant
K|T_{\sigma}^{n-1}v-T_{\sigma}^{n-1}w|$. Since $K$ is order-preserving, we can
iterate on the last inequality to obtain
$|T_{\sigma}^{n}v-T_{\sigma}^{n}w|\leqslant K^{n}|v-w|$. Since $\|\cdot\|$ is
a lattice norm, applying (E1) on page 7.4 yields

$\|T_{\sigma}^{n}v-T_{\sigma}^{n}w\|\leqslant\|K^{n}|v-w|\|\leqslant
M\lambda^{n}\|v-w\|.$ (18)

As $\lambda\in[0,1)$, the map $T^{n}_{\sigma}$ is a contraction on $V$ for
sufficiently large $n$. Since $V$ is a closed in $E$, a standard extension to
the Banach fixed point theorem (see, e.g., Goebel and Kirk, (1990), p. 9)
yields global stability of $T_{\sigma}$ on $V$.

Regarding global stability of $T$, we use (17) to obtain

$T_{\sigma}\,v=T_{\sigma}\,w+T_{\sigma}\,v-T_{\sigma}\,w\leqslant
T_{\sigma}\,w+|T_{\sigma}\,v-T_{\sigma}\,w|\leqslant Tw+K|v-w|.$ (19)

Taking the supremum gives $Tv-Tw\leqslant K|v-w|$. Reversing the roles of $v$
and $w$ yields $|Tv-Tw|\leqslant K|v-w|$, which is identical to (17) after
replacing $T_{\sigma}$ with $T$. Repeating the analysis we just provided for
global stability of $T_{\sigma}$, but replacing $T_{\sigma}$ with $T$, we see
that $T$ is also globally stable on $V$. ∎

###### Proof of Theorem 7.4.

Let $E$ be a Banach lattice and let $(V,\mathbbm{T})$ have the stated
properties. Since $E$ is a partially ordered space, it suffices to check the
conditions of Theorem 7.3. But these have already been verified in Lemma 8.2.
Hence the conditions of Theorem 7.3 hold, which in turn yields all claims in
Theorem 7.4. ∎

##  9\. Applications

In this section we illustrate how ADP optimality results stated above can be
applied. In what follows, we call a linear self-map $L$ on an ordered vector
space $E$ positive if $v\in E_{+}$ implies $Lv\in E_{+}$. When $E$ is a Banach
space, the spectral radius of a bounded linear operator $K$ from $E$ to itself
will be denoted by $\rho(K)$.

###  9.1. Application: Optimality of MDPs

Here we show how ADP theory can be used to establish optimality for the MDP
model described in Section 3.2. Our purpose is to illustrate ideas in a
standard setting before turning to more sophisticated ones.

The standard MDP optimality results state the following: the MDP value
function $v^{*}(x)\coloneq\max_{\sigma\in\Sigma}\,v_{\sigma}(x)$ is the unique
solution to the MDP Bellman equation (2), that there exists at least one
policy $\sigma$ such that $v_{\sigma}=v^{*}$ (i.e., one optimal policy), and
that a policy $\sigma\in\Sigma$ is optimal if and only if (4) holds (see,
e.g., Puterman, (2005)).

The MDP optimality results can be obtained from the theory in Section 7. To
see this, let $(\mathbbm{R}^{\mathsf{X}},\mathbbm{T})$ be the ADP generated by
this MDP model, as described in Section 3.2. We can write
$T_{\sigma}\in\mathbbm{T}$ as $T_{\sigma}\,v=r_{\sigma}+\beta P_{\sigma}\,v$.
It follows that for each $v,w\in\mathbbm{R}^{\mathsf{X}}$ we have
$|T_{\sigma}\,v-T_{\sigma}\,w|\leqslant\beta P|v-w|$. From this bound it is
simple to verify that, with $\|\cdot\|$ as the supremum norm, each
$T_{\sigma}$ and the Bellman operator $T\coloneq\bigvee_{\sigma}T_{\sigma}$
are all contraction mappings on the Banach lattice
$(\mathbbm{R}^{\mathsf{X}},\leqslant,\|\cdot\|)$. Hence all of the conditions
of Theorem 7.3 hold, so $V_{\Sigma}=\\{v_{\sigma}\\}$ has a greatest element
$v^{*}$, this function $v^{*}$ is the unique solution to the ADP Bellman
equation $Tv=v$, and Bellman’s principle of optimality holds.

We can easily translate these findings back into the standard MDP optimality
results. For example, under the pointwise partial order $\leqslant$ on
$\mathbbm{R}^{\mathsf{X}}$, the statement that $v^{*}$ is a greatest element
of $V_{\Sigma}$ is equivalent to the statement that $v^{*}=v_{\sigma}$ for
some $\sigma\in\Sigma$ and, in addition,
$v^{*}(x)=\max_{\sigma\in\Sigma}\,v_{\sigma}(x)$ for all $x\in\mathsf{X}$.

###  9.2. Application: Non-EU Discrete Choice

Some studies have found incompatibilities between data and predictions of
models founded on additively separable preferences. A recent example is Lu et
al., (2023), which re-examines the structural estimation problem of Rust,
(1987) and finds that the data rejects time additive rewards. To further this
line of analysis, we return to the discrete choice expected value Bellman
equation in Section 3.5, which was motivated by structural estimation, while
replacing mathematical expectation with a general certainty equivalent
operator (so that preferences can fail to be additively separable).

In what follows, if $M$ is a metric space, then $bM$ denotes the set of
bounded Borel measurable functions from $M$ to $\mathbbm{R}$. We combine $bM$
with the pointwise order $\leqslant$ and the supremum norm, denoted by
$\|\cdot\|$.

We adopt setting of Section 3.5, where $\mathsf{X}$ is a metric space,
$\mathsf{A}$ is a finite choice set,
$\mathsf{G}\coloneq\mathsf{X}\times\mathsf{A}$ and
$r\colon\mathsf{G}\to\mathbbm{R}$ is a reward function. However, we modify the
Bellman equation (14) for the post-action value function to

$g(x,a)=(\mathcal{E}Hg)(x,a)\quad\text{where
}(Hg)(x^{\prime})\coloneq\max_{a^{\prime}\in\mathsf{A}}\left[r(x^{\prime},a^{\prime})+\beta
g(x^{\prime},a^{\prime})\right]$ (20)

and $\mathcal{E}$ is a certainty equivalent operator mapping $b\mathsf{X}$
into $b\mathsf{G}$, in the sense that $\mathcal{E}$ is order-preserving and
$\mathcal{E}\lambda=\lambda$ whenever $\lambda$ is constant. We assume in
addition that $\mathcal{E}$ is constant subadditive, meaning that
$\mathcal{E}(f+\lambda)\leqslant\mathcal{E}f+\lambda$ for all $f\in
b\mathsf{X}$ and $\lambda\in\mathbbm{R}_{+}$.

Let $\Sigma$ be the set of Borel measurable maps from $\mathsf{X}$ to
$\mathsf{A}$. Given $\sigma\in\Sigma$, we set

$(T_{\sigma}\,g)(x,a)=(\mathcal{E}H_{\sigma}\,g)(x,a)\quad\text{where
}(H_{\sigma}\,g)(x^{\prime})\coloneq r(x^{\prime},\sigma(x^{\prime}))+\beta
g(x^{\prime},\sigma(x^{\prime})).$

The pair $(b\mathsf{G},\\{T_{\sigma}\\}_{\sigma\in\Sigma})$ is an ADP and
$\sigma\in\Sigma$ is $g$-greedy whenever

$\sigma(x)\in\operatorname*{arg\,max}_{a^{\prime}\in\mathsf{A}}\left[r(x^{\prime},a^{\prime})+\beta
g(x^{\prime},a^{\prime})\right]\quad\text{for all }x\in\mathsf{X}.$

(A measurable selection theorem can be used to obtain Borel measurability of
$\sigma$. See, for example, Aliprantis and Border, (1999), Theorem 17.18.)

The ADP Bellman operator $T$ satisfies $Tg=\bigvee_{\sigma}T_{\sigma}\,g$ for
all $g\in b\mathsf{G}$. Suprema in $(b\mathsf{G},\leqslant)$ equal pointwise
suprema, from which we obtain $Tg=\mathcal{E}Hg$. Hence any fixed point of $T$
solves the original Bellman equation (14).

Fix $f,g\in b\mathsf{G}$. Since $\mathcal{E}$ and $H_{\sigma}$ are order-
preserving, we have

$T_{\sigma}\,f=\mathcal{E}H_{\sigma}(g+f-g)\leqslant\mathcal{E}H_{\sigma}(g+\|f-g\|)\leqslant\mathcal{E}(H_{\sigma}\,g+\beta\|f-g\|).$

Using constant subadditivity of $\mathcal{E}$ and rearranging gives

$T_{\sigma}\,f-T_{\sigma}\,g\leqslant\mathcal{E}\beta\|f-g\|=\beta\|f-g\|.$

Reversing the roles of $f$ and $g$ gives
$|T_{\sigma}\,f-T_{\sigma}\,g|\leqslant\beta\|f-g\|$. A simple argument (see
(19) in the proof of Lemma 8.2) extends this bound to $T$, in the sense that
$|Tf-Tg|\leqslant\beta\|f-g\|$ for all $f,g\in b\mathsf{G}$. Hence $T$ and all
$T_{\sigma}$ are contraction maps on $b\mathsf{G}$. The conditions of Theorem
7.3 are all verifed, from which it follows that

######  Proposition 9.1.

If $\mathcal{E}$ is constant subadditive, then the fundamental Bellman
optimality properties hold for the non-EU discrete choice model, and value
function iteration and Howard policy iteration both converge.

As an illustration, suppose that $\mathcal{E}$ is the risk-sensitive certainty
equivalent

$(\mathcal{E}f)(x,a)\coloneq\frac{1}{\theta}\ln\left\\{\int\exp\left[\theta
f(x^{\prime})\right]P(x,a,\mathop{}\\!\mathrm{d}x^{\prime})\right\\}\qquad((x,a)\in\mathsf{G})),$

where $P$ is a stochastic kernel from $\mathsf{G}$ to $\mathsf{X}$ and
$\theta$ is a nonzero constant. This choice of certainty equivalent is
constant subadditive, so, among other things, Proposition 9.1 tells us that
$\sigma\in\Sigma$ is optimal if and only if

$\sigma(x)\in\operatorname*{arg\,max}_{a^{\prime}\in\mathsf{A}}\left[r(x^{\prime},a^{\prime})+\beta
g^{*}(x^{\prime},a^{\prime})\right]\quad\text{for all }x\in\mathsf{X},$

where $g^{*}$ is the unique solution to the functional equation

$g(x,a)=\frac{1}{\theta}\ln\left\\{\int\exp\left\\{\theta\max_{a^{\prime}\in\mathsf{A}}\left[r(x^{\prime},a^{\prime})+\beta
g(x^{\prime},a^{\prime})\right]\right\\}P(x,a,\mathop{}\\!\mathrm{d}x^{\prime})\right\\}$

in the value space $b\mathsf{G}$.

Another example of a nonlinear certainty equivalent operator is the quantile
operator studied in de Castro and Galvao, (2019) and de Castro et al., (2022),
which allows for separation of intertemporal elasticity of substitution and
risk aversion. This certainty equivalent is also constant subadditive, so
Proposition 9.1 extends the results in de Castro and Galvao, (2019).

###  9.3. Application: A Firm Exit Problem

We consider a well-known firm exit problem studied by Jovanovic, (1982),
Hopenhayn and Prescott, (1992), Alessandria et al., (2021), Sterk et al.,
(2021) and many other authors. We introduce the following extensions to the
original decision problem: (i) firm profits depend on an aggregate shock, as
well as a firm-specific shock and a cross-sectional distribution, (ii) the
interest rate is allowed to vary over time, and (iii) the outside option of
the firm is permitted to depend on aggregates and the cross-section.

Analogous to Jovanovic, (1982) (see eq. (3.2) of that reference), for a firm
that receives current profit $\pi(s,\mu,z)$ and then transitions to the next
period, where management will choose to either (i) exit and receive outside
option $q(\mu^{\prime},z^{\prime})$, or (ii) continue, the maximal expected
firm value $v(s,\mu,z)$ obeys

$v(s,\mu,z)=\pi(s,\mu,z)+\beta(\mu,z)\,\mathbbm{E}_{(s,\mu,z)}\max\\{q(\mu^{\prime},z^{\prime}),v(s^{\prime},\mu^{\prime},z^{\prime})\\}.$
(21)

Here $s$ is an idiosyncratic state for the firm that takes values in set $S$,
$\mu$ is a cross-sectional distribution taking values in a (possibly infinite-
dimensional) space $D$, $z$ is an aggregate shock taking values in set $Z$,
and $\pi(s,\mu,z)$ is current profit. Primes denote next period values. The
discount factor $\beta$ obeys

$\beta(\mu,z)=\frac{1}{1+r(\mu,z)}\quad\text{where}\quad
r(\mu,z)\coloneq\text{ the current interest rate}.$

Let $x\coloneq(s,\mu,z)$ take values in $\mathsf{X}\coloneq S\times D\times
Z$. Let $\mathcal{B}$ be a $\sigma$-algebra over $\mathsf{X}$ that makes
$\pi,\beta$ and the transition probabilies measurable. We can rewrite the
dynamics as $x^{\prime}=P(x,\cdot)$, meaning that $P$ is a stochastic kernel
$(\mathsf{X},\mathcal{B})$ and the next period composite state $x^{\prime}$ is
drawn from distribution $P(x,\cdot)$. With this notation, (21) becomes

$v(x)=\pi(x)+\beta(x)\int\max\left\\{q(x^{\prime}),v(x^{\prime})\right\\}P(x,\mathop{}\\!\mathrm{d}x^{\prime})\qquad(x\in\mathsf{X}).$
(22)

A $v$ that solves (22) gives firm valuation at each state under an optimal
management strategy. In this setting, a management strategy is a
$\mathcal{B}$-measurable map $\sigma$ from $\mathsf{X}$ to $\\{0,1\\}$ with
$\sigma(x)=1$ indicating the decision to exit at state $x$ and $\sigma(x)=0$
indicating the decision to continue. Let $\Sigma$ be the set of all management
strategies. Analogous to (22), at current state $x$, a fixed management
strategy $\sigma$ yields firm value $v_{\sigma}(x)$, where $v_{\sigma}$
satisfies the recursion
$v_{\sigma}(x)=\pi(x)+\beta(x)\int[\sigma(x^{\prime})q(x^{\prime})+(1-\sigma(x^{\prime}))v_{\sigma}(x^{\prime})]P(x,\mathop{}\\!\mathrm{d}x^{\prime})$
for all $x\in\mathsf{X}$. Equivalently, $v_{\sigma}$ is a fixed point of
$T_{\sigma}$ defined by

$T_{\sigma}\,v=\pi+K(\sigma q+(1-\sigma)v)$ (23)

where $Kv(x)\coloneq\beta(x)\int
v(x^{\prime})P(x,\mathop{}\\!\mathrm{d}x^{\prime})$ is the discount operator
determined by $\beta$ and $P$. The firm value function is defined by
$v^{*}=\bigvee_{\sigma\in\Sigma}v_{\sigma}$. A policy $\sigma\in\Sigma$ is
called optimal for the firm problem if $v_{\sigma}=v^{*}$.

We suppose there exists a $\sigma$-finite measure $\nu$ on
$(\mathsf{X},\mathcal{B})$ such that $\pi,q$ and $\beta$ are nonnegative
elements of $L_{1}\coloneq L_{1}(\mathsf{X},\mathcal{B},\nu)$, and that $K$
maps $L_{1}$ to itself. These restrictions are mild, since they allow the
primitives to be discontinuous and unbounded above. We endow $L_{1}$ with the
$\nu$-a.e. pointwise order $\leqslant$, so that $f\leqslant g$ means
$\nu\\{f>g\\}=0$. The operator $T_{\sigma}$ understood as a self-map on
$L_{1}$.

We wish to characterize the maximum value of the firm and the optimal
management strategy, as well as find convergent algorithms for computing these
objects.

######  Assumption 9.1.

The discount operator has spectral radius strictly less than one.

Assumption 9.1, which we shall use to establish optimality below, is weaker
than that found in Hansen and Scheinkman, (2012) and related sources, since we
impose no irreducibility or compactness conditions on $K$. (Later, we show
that, when such conditions _are_ in force, Assumption 9.1 is both necessary
and sufficient for optimality.)

Let $V$ be the positive cone of $L_{1}$.

######  Proposition 9.2.

If Assumption 9.1 holds, then there exists a unique solution $v^{*}$ in $V$ to
the Bellman equation (22), $v^{*}$ is the firm value function
$\bigvee_{\sigma}v_{\sigma}$, and a policy $\sigma$ is optimal for the firm
problem if and only if

$\sigma=\mathbbm{1}\\{q\geqslant v^{*}\\}.$ (24)

In addition, Howard policy iteration and value function iteration both
converge to $v^{*}$.

###### Proof.

To prove Proposition 9.2, we embed the firm problem in an ADP setting. Given
$v\in V$, the set $\\{T_{\sigma}\,v\\}_{\sigma\in\Sigma}$ has greatest element
$\pi+K(q\vee v)$, which is attained by the $v$-greedy policy
$\sigma=\mathbbm{1}\\{q\geqslant v\\}$. It follows that, with
$\mathbbm{T}\coloneq\\{T_{\sigma}:\sigma\in\Sigma\\}$, the pair
$(V,\mathbbm{T})$ forms an ADP.

We claim that $(V,\mathbbm{T})$ is eventually Blackwell contracting (see
Section 7.4). To see this, observe that for fixed $\sigma\in\Sigma$ and
$v,h\in V$ we have

$T_{\sigma}\,(v+h)=\pi+K[\sigma q+(1-\sigma)(v+h)]\leqslant\pi+K[\sigma
q+(1-\sigma)v]+Kh=T_{\sigma}\,v+Kh.$

Since $K$ is a positive linear operator and $\rho(K)<1$, the ADP
$(V,\mathbbm{T})$ is an eventually Blackwell contracting.

It follows that, in this setting, the conditions of Theorem 7.4 also hold, so

  1. (i)

$V_{\Sigma}\coloneq\\{v_{\sigma}\\}$ has a greatest element $v^{*}$,

  2. (ii)

$v^{*}$ is the unique solution to the ADP Bellman equation $v^{*}=Tv^{*}$,

  3. (iii)

a policy $\sigma$ is optimal for the ADP $(V,\mathbbm{T})$ if and only if
$\sigma$ is $v^{*}$-greedy, and

  4. (iv)

Howard policy iteration and value function iteration both converge to $v^{*}$.

By the definition of $T_{\sigma}$, the ADP Bellman operator obeys
$Tv=\bigvee_{\sigma\in\Sigma}T_{\sigma}\,v=\pi+K(q\vee v)$. But this coincides
with (22), so, by (ii), $v^{*}$ is the unique solution in $V$ to the original
firm Bellman equation (22). Now observe that $\sigma$ obeys (24) if and only
if

$K(\sigma q+(1-\sigma)v^{*})\geqslant K(\tau q+(1-\tau)v^{*})\quad\text{for
all }\tau\in\Sigma,$

which implies that $T_{\sigma}\,v^{*}\geqslant T_{\tau}\,v^{*}$ for all
$\tau\in\Sigma$. In other words, $\sigma$ obeys (24) if and only if $\sigma$
is $v^{*}$-greedy, which, by (iii), is equivalent to optimality. This
completes the proof of Proposition 9.2. ∎

To show that our assumptions are weak, we now prove that, under some side
conditions, well-posedness fails whenever Assumption 9.1 fails. This means
that Assumption 9.1 is necessary for the dynamic program to be well-defined.

######  Proposition 9.3.

Let $\pi$ be nonzero and let $K$ be weakly compact and irreducible on $L_{1}$.
In this setting, if $(V,\mathbbm{T})$ is well-posed, then Assumption 9.1
holds.

###### Proof.

Let $\pi$ be nonzero and let $K$ be weakly compact and irreducible on $L_{1}$.
Let $K^{\prime}$ be the adjoint of $K$ and let $\lambda$ be the spectral
radius. By the Krein–Rutman theorem (see, in particular, Lemma 4.2.11 of
Meyer-Nieberg, (2012)), there exists an $e\in L_{\infty}(\nu)$ such that
$K^{\prime}e=\lambda e$ and, in addition, $\left\langle{e,f}\right\rangle>0$
for all nonzero nonnegative $f\in L_{1}$. Consider the policy $\sigma\equiv
0$. Under this policy we have $T_{\sigma}\,v=\pi+Kv$. If $(V,\mathbbm{T})$ is
well-posed, then there exists a solution $v\in V$ to $v=\pi+Kv$ in $V$. Since
$\pi$ is nonzero and $v=\pi+Kv\geqslant\pi$, the same is true for $v$. Now
observe that

$\left\langle{e,v}\right\rangle=\left\langle{e,\pi}\right\rangle+\left\langle{e,Kv}\right\rangle=\left\langle{e,\pi}\right\rangle+\left\langle{K^{\prime}e,v}\right\rangle=\left\langle{e,\pi}\right\rangle+\lambda\left\langle{e,v}\right\rangle.$

Since $v$ and $\pi$ are nonnegative and nonzero, it must be that
$\left\langle{e,\pi}\right\rangle>0$ and $\left\langle{e,v}\right\rangle>0$.
Therefore $\lambda$ satisfies $(1-\lambda)\alpha=\beta$ for $\alpha,\beta>0$.
Hence $\lambda<1$. ∎

##  10\. Extension: Restricted Greedy Policies

The preceding theory assumes that greedy policies exist. In some applications
greedy policies only exist on a subset of the value space. In this section we
provide theory that can address such situations.

###  10.1. Theory

We define a pre-ADP to be a pair $(V,\mathbbm{T})$, where

  1. (i)

$V=(V,\preceq)$ is a nonempty partially ordered set and

  2. (ii)

$\mathbbm{T}=\\{T_{\sigma}:\sigma\in\Sigma\\}$ is a family of order-preserving
self-maps on $V$.

The only difference between pre-ADPs and ADPs is that existence of greedy
policies is not enforced.

In line with our definitions for ADPs, we call a pre-ADP $(V,\mathbbm{T})$
downward stable if each $T_{\sigma}\in\mathbbm{T}$ is downward stable on $V$
and well-posed if each $T_{\sigma}\in\mathbbm{T}$ has a unique fixed point
$v_{\sigma}\in V$. In this setting $v_{\sigma}$ is called the
$\sigma$-lifetime value function and we set
$V_{\Sigma}\coloneq\\{v_{\sigma}:\sigma\in\Sigma\\}$. Also, $\sigma\in\Sigma$
is called optimal if $v_{\sigma}$ is a greatest element of $V_{\Sigma}$.

As for ADPs, given pre-ADP $(V,\mathbbm{T})$ and $v\in V$, a policy $\sigma$
in $\Sigma$ is called $v$-greedy if $T_{\sigma}\,v\succeq T_{\tau}\,v$ for all
$\tau\in\Sigma$. The Bellman operator associated with $(V,\mathbbm{T})$ is
defined at $v\in V$ by $Tv\coloneq\bigvee_{\sigma}T_{\sigma}\,v$ whenever the
supremum exists.

We can now state our main optimality result for pre-ADPs. The implications of
the theorem essentially match the fundamental Bellman optimality properties
(B1)–(B3) in Section 4.2.

######  Theorem 10.1.

Let $(V,\mathbbm{T})$ be a well-posed and downward stable pre-ADP with Bellman
operator $T$. If there exists a $V_{G}\subset V$ such that

  1. (i)

for each $v\in V_{G}$, there exists at least one $v$-greedy policy, and

  2. (ii)

$T$ has at least one fixed point in $V_{G}$,

then the following statements are true:

  1. (a)

$V_{\Sigma}$ has a greatest element $v^{*}$ and, moreover, $v^{*}\in V_{G}$,

  2. (b)

$v^{*}$ is the unique fixed point of the Bellman operator in $V_{G}$, and

  3. (c)

$\sigma\in\Sigma$ is optimal if and only if $\sigma$ is $v^{*}$-greedy.

###### Proof.

Let $v^{*}$ be a fixed point of $T$ in $V_{G}$. By condition (i), there exists
a $\sigma\in\Sigma$ such that $T_{\sigma}\,v^{*}=Tv^{*}$. But then
$T_{\sigma}\,v^{*}=v^{*}$, so, by well-posedness, $v^{*}=v_{\sigma}$. Hence
$v^{*}\in V_{\Sigma}$. Moreover, if $\tau\in\Sigma$, then
$T_{\tau}\,v^{*}\preceq Tv^{*}=v^{*}$, so, by downward stability,
$v_{\tau}\preceq v^{*}$. Hence $v^{*}$ is a greatest element of $V_{\Sigma}$.
Since greatest elements are unique, the only fixed point of $T$ in $V_{G}$ is
the greatest element $v^{*}$. This proves (a) and (b).

Regarding (c), $\sigma$ is optimal if and only if $v_{\sigma}=v^{*}$. Since
$v_{\sigma}$ is the unique fixed point of $T_{\sigma}$ in $V_{G}$ and $v^{*}$
is the unique fixed point of $T$ in $V_{G}$, this is equivalent to
$T_{\sigma}\,v^{*}=Tv^{*}$, which is in turn equivalent to the statement that
$\sigma$ is $v^{*}$-greedy. ∎

###  10.2. Application: Structural Estimation with Continuous Actions

As an application of Theorem 10.1 we consider an extension of the structural
estimation model in Section 3.5. The Bellman equation is

$g(x,a)=\int\left\\{\max_{a^{\prime}\in\mathsf{A}}\left[r(x^{\prime},a^{\prime})+\beta(x^{\prime})g(x^{\prime},a^{\prime})\right]\right\\}P(x,a,\mathop{}\\!\mathrm{d}x^{\prime})$
(25)

where $(x,a)\in\mathsf{G}\coloneq\mathsf{X}\times\mathsf{A}$. As before
$\mathsf{X}$ is a metric space, $r$ is a bounded reward function on
$\mathsf{G}$ and $P(x,a,\mathop{}\\!\mathrm{d}x^{\prime})$ is a Borel
probability measure on $\mathsf{X}$ for each $(x,a)\in\mathsf{G}$. We have
dropped the assumption that $\beta$ is constant, allowing it to depend on the
state. Also, we no longer require that $\mathsf{A}$ is finite. Instead we
assume that $\mathsf{A}$ is a compact metric space.

Let $V$ be the set of all bounded Borel measurable functions in
$\mathbbm{R}^{\mathsf{G}}$ and let $V_{G}$ be all continuous functions in $V$.
Let $\|\cdot\|$ be the supremum norm. We assume that

  1. (a1)

$r$ and $\beta$ are continuous,

  2. (a2)

the function $(x,a)\mapsto\int
h(x^{\prime})P(x,a,\mathop{}\\!\mathrm{d}x^{\prime})$ is Borel measurable
(resp., continuous) on $\mathsf{G}$ whenever $h$ is Borel measurable (resp.,
continuous) on $\mathsf{X}$, and

  3. (a3)

the self-map $K$ on $V$ defined by

$(Kf)(x,a)=\int\beta(x^{\prime})\max_{a^{\prime}\in\mathsf{A}}f(x^{\prime},a^{\prime})P(x,a,\mathop{}\\!\mathrm{d}x^{\prime})\qquad(x,a)\in\mathsf{G}$

obeys $\lim_{n\to\infty}\|K^{n}f\|=0$ for all $f\in V$.

Conditions (a1) and (a2) are regularity conditions, while (a3) is a
discounting condition. Note that (a3) generalizes the traditional assumption
that $\beta$ is constant and strictly less than one. (In this setting it is
easily proved that $K$ is a contraction map on $V$ and $K0=0$, which in turn
implies (a3).)

Let $\Sigma$ be the set of all Borel measurable maps from $\mathsf{X}$ to
$\mathsf{A}$ and, given $\sigma\in\Sigma$, let $T_{\sigma}$ be defined at
$g\in V$ by and $(x,a)\in\mathsf{G}$ by

$(T_{\sigma}\,g)(x,a)=\int\left\\{\left[r(x^{\prime},\sigma(x^{\prime}))+\beta(x^{\prime})g(x^{\prime},\sigma(x^{\prime}))\right]\right\\}P(x,a,\mathop{}\\!\mathrm{d}x^{\prime})$

By (a1)–(a2) and boundedness of $r$, $T_{\sigma}$ is an order-preserving self-
map on $V$, so $(V,\\{T_{\sigma}\\}_{\sigma\in\Sigma})$ is a pre-ADP. For each
$g\in V_{G}$, we can construct a $g$-greedy policy by taking a
$\sigma\in\Sigma$ such that

$\sigma(x)\in\operatorname*{arg\,max}_{a\in\mathsf{A}}\\{r(x,a)+\beta(x)g(x,a)\\}\quad\text{for
all }x\in\mathsf{X}.$

Such a $\sigma$ exists by continuity of $r$ and $g$ combined with the
measurable selection theorem (see Aliprantis and Border, (1999), Theorem
17.18).

Let $T$ be the Bellman operator, so that
$Tg\coloneq\bigvee_{\sigma}T_{\sigma}\,g$. When evaluated at a $g$-greey
policy $\sigma$, we have $T_{\sigma}\,g=Tg$, which yields

$(Tg)(x,a)=\int\left\\{\max_{a^{\prime}\in\mathsf{A}}\left[r(x^{\prime},a^{\prime})+\beta(x^{\prime})g(x^{\prime},a^{\prime})\right]\right\\}P(x,a,\mathop{}\\!\mathrm{d}x^{\prime}).$

It follows that solutions to $Tg=g$ solve the original Bellman equation (25).

To verify the conditions of Theorem 10.1, we need to confirm that each
$T_{\sigma}$ has a unique fixed point in $V$, and that $T$ has a fixed point
in $V_{G}$. To this end, fix $\sigma\in\Sigma$ and $f,g\in V$. We have

$|(T_{\sigma}\,f)(x,a)-(T_{\sigma}\,g)(x,a)|\leqslant\int\beta(x^{\prime})|f(x^{\prime},\sigma(x^{\prime}))-g(x^{\prime},\sigma(x^{\prime}))|P(x,a,\mathop{}\\!\mathrm{d}x^{\prime})$

Hence, using $K$ from (a3),

$|T_{\sigma}\,f-T_{\sigma}\,g|\leqslant K|f-g|.$

From the proof of Lemma 8.2 we see that $T$ and every $T_{\sigma}$ are
globally stable on $V$. Since $V_{G}$ is a closed subset of $V$ and $T$ maps
$V_{G}$ to itself, we find that the fixed point of $T$ is in $V_{G}$. Hence
all of the conditions of Theorem 10.1 hold, and so do its conclusions.

###  10.3. Application: Concave Solutions

In this section we extend some of the optimality results in Bäuerle and
Jaśkiewicz, (2018), giving conditions under which a unique and continuous
optimal policy exists. We replace the specific model in Bäuerle and
Jaśkiewicz, (2018) with a more generic framework, while preserving certain
concavity and continuity properties. (Our framework is also similar to the
contractive models in Bertsekas, (2022), to which we add uniqueness, concavity
and continuity results under additional assumptions.)

Consider the abstract MDP setting of Section 3.3 but now suppose instead that
$\mathsf{X}$ and $\mathsf{A}$ are nonempty convex subset of finite-dimensional
vector space, and that the correspondence $\Gamma$ is nonempty and compact-
valued. Let $\varphi\colon\mathsf{X}\to[1,\infty)$ be Borel measurable. Let

  * •

$V$ be all Borel measurable $v\colon\mathsf{X}\to\mathbbm{R}$ such that

$\|f\|\coloneq\sup_{x\in\mathsf{X}}\frac{|f(x)|}{\varphi(x)}<\infty\quad\text{and}$

  * •

$\Sigma=$ all Borel measurable $\sigma\colon\mathsf{X}\to\mathsf{A}$ with
$\sigma(x)\in\Gamma(x)$ for all $x\in\mathsf{X}$.

Let $V_{G}$ be the continuous concave functions in $V$. We require that (9)
holds, that $\mathsf{G}$ is convex and, for some constants $c,d,\beta$ with
$\beta\in[0,1)$,

  1. (C1)

$(x,a)\mapsto B(x,a,v)$ is Borel measurable for all $v\in V$, and concave and
continuous for all $v\in V_{G}$,

  2. (C2)

$a\mapsto B(x,a,v)$ is strictly concave for all $x\in\mathsf{X}$ and $v\in
V_{G}$,

  3. (C3)

$|B(x,a,v)-B(x,a,w)|\leqslant\beta\|v-w\|\varphi(x)$ for all
$(x,a)\in\mathsf{G}$ and $v,w\in V$, and

  4. (C4)

$|B(x,a,v)|\leqslant c+d\varphi(x)$ for all $(x,a)\in\mathsf{G}$ and $v\in V$.

For each $\sigma\in\Sigma$ we define $T_{\sigma}$ by
$(T_{\sigma}\,v)(x)=B(x,\sigma(x),v)$ for all $x\in\mathsf{X}$ and $v\in V$.
By (C1) and (C4), $T_{\sigma}$ is a self-map on $V$. By (9), $T_{\sigma}$ is
order-preserving in the usual pointwise order. Hence $(V,\mathbbm{T})$ is a
pre-ADP. Moreover, (C3) implies that, for arbitrary $v,w\in V$ and
$\sigma\in\Sigma$, we have

$|T_{\sigma}\,v-T_{\sigma}\,w|\leqslant\beta\|v-w\|\varphi,$ (26)

and hence $T_{\sigma}$ is a contraction on the complete metric space
$(V,\|\cdot\|)$, which in turn tells us that $(V,\mathbbm{T})$ is well-posed
and downward stable (in fact order stable, by Lemma 8.1).

Now fix $v\in V_{G}$ and consider the ADP Bellman operator
$T=\bigvee_{\sigma}T_{\sigma}$, which, under the current pointwise partial
order, reduces to $(Tv)(x)=\max_{a\in\Gamma(x)}B(x,a,v)$. The maximum exists
by (C1). In fact, by (C1) and the theorem of the maximum (see, e.g.,
Aliprantis and Border, (1999), $Tv$ is also continuous and the uniquely
defined single-valued function
$\sigma(x)=\operatorname*{arg\,max}_{a\in\Gamma(x)}B(x,a,v)$ is continuous,
which shows that a unique $v$-greedy policy exists for each $v\in V_{G}$ and
moreover, that policy is continuous.

A straightforward extension of the arguments in Ch. 12 of Stachurski, (2022)
shows that, under (C1)–(C4), $T$ is a contractive self-map on the complete
metric space $V_{G}$ (using the same norm). Hence $T$ has a fixed point in
$V_{G}$. Applying Theorem 10.1, we can now state the following results for the
ADP $(V,\mathbbm{T})$:

######  Proposition 10.2.

Under conditions (C1)–(C4), the fundamental Bellman optimality properties
hold. Moreover, the value function $v^{*}$ is continuous and concave and the
optimal policy is unique and continuous.

Here uniqueness follows from Bellman’s principle of optimality and uniqueness
of of greedy policies for $v\in V_{G}$.

###  10.4. Application: LQ Models

In this section we show how a generic linear quadratic (LQ) problem can be
handled via Theorem 10.1.

Let $\mathcal{P}$ be all real positive semidefinite $k\times k$ matrices. Let
$A$ be in $\mathbbm{R}^{k\times k}$, $B$ be in $\mathbbm{R}^{m\times k}$, $Q$
be an element of $\mathcal{P}$, and $R$ be a real positive definite $m\times
m$ matrix. A function $v$ is said to solve the LQ Bellman equation if

$v(x)=\min_{u\in\mathbbm{R}^{m}}\left\\{u^{\top}Ru+x^{\top}Qx+v(Ax+Bu)\right\\}\quad\text{for
all }x\in\mathbbm{R}^{k},$ (27)

where $u\in\mathbbm{R}^{m}$ is a control and $v(x)=x^{\top}Px$ for some
$P\in\mathcal{P}$. Below we use the fact that, for all $x\in\mathbbm{R}^{k}$,
the unique minimizer in (27) is

$u=Fx\quad\text{ where }F\coloneq-(B^{\top}PB+R)^{-1}B^{\top}PA.$ (28)

Given $P\in\mathcal{P}$, we call the control $F$ in (28) the $P$-minimal
control.

Optimization requires driving the state toward zero. This fact motivates us to
define the set of policies as

$\Sigma\coloneq\text{ all $F\in\mathbbm{R}^{m\times k}$ such that
}\rho(A+BF)<1.$

The lifetime value of $F\in\Sigma$ at initial condition
$x_{0}\in\mathbbm{R}^{k}$ is

$v_{F}(x_{0})\coloneq\sum_{t=0}^{\infty}\left[x_{t}^{\top}F^{\top}RFx_{t}+x_{t}^{\top}Qx_{t}\right]\;\text{
with $x_{t}\coloneq(A+BF)^{t}x_{0}$}.$ (29)

A policy $F$ is called LQ-optimal if $v_{F}(x)\leqslant v_{S}(x)$ for all
$S\in\Sigma$ and $x\in\mathbbm{R}^{k}$.

Let $C$ be such that $C^{\top}C=Q$. The following results are standard (see,
e.g., Bertsekas, (2012), Proposition 3.1.1):

######  Theorem 10.3.

If $(A,B)$ is controllable and $(A,C)$ is observable, then

  1. (i)

there exists a unique solution $P^{*}$ in $\mathcal{P}$ to the Riccati
equation

$P=A^{\top}(P-PB(B^{\top}PB+R)^{-1}B^{\top}P)A+Q.$ (30)

  2. (ii)

$v^{*}$ defined by $v^{*}(x)=x^{\top}P^{*}x$ satisfies the LQ Bellman
equation, and

  3. (iii)

the $P^{*}$-minimal control is LQ-optimal.

We refer to Bertsekas, (2012) for the definitions of observability and
controllability. We prove the optimality components (ii)–(iii) of Theorem 10.3
via Theorem 10.1.

First we endow $\mathcal{P}$ with a _reversed_ Loewner partial order
$\preccurlyeq$ on the set of $k\times k$ matrices, so that $A\preccurlyeq B$
means $A-B\in\mathcal{P}$. (We reverse the Loewner order to convert
minimization into maximization.) Given $F\in\Sigma$, we define the policy
operator $T_{F}$ from $\mathcal{P}$ to itself by

$T_{F}\,P=F^{\top}RF+Q+(A+BF)^{\top}P(A+BF)\qquad(P\in\mathcal{P}).$

Let $\mathbbm{T}$ be the set of all policy operators as $F$ ranges over
$\Sigma$.

######  Lemma 10.4.

The pair $(\mathcal{P},\mathbbm{T})$ is a well-posed pre-ADP. Moreover, for
$T_{F}\in\mathbbm{T}$, the unique fixed point $P_{F}\in\mathcal{P}$ is such
that $v_{F}(x)=x^{\top}P_{F}\,x$ for all $x\in\mathbbm{R}^{k}$.

###### Proof.

Fix $F\in\Sigma$. We write $T_{F}=H+LP$, where $H\coloneq F^{\top}RF+Q$ and
$L$ maps $P$ into $(A+BF)^{\top}P(A+BF)$. Elementary calculations show that
$T_{F}$ is an order preserving self-map on $(\mathcal{P},\preccurlyeq)$. Since
$\rho(A+BF)<1$, we have $\rho(L)<1$, so $T_{F}$ has the unique fixed point
$P_{F}=\sum_{t=0}^{\infty}L^{t}H$. Moreover, for given
$x_{0}\in\mathbbm{R}^{k}$, we obtain

$x_{0}^{\top}P_{F}\,x_{0}=\sum_{t=0}^{\infty}x_{0}^{\top}L^{t}Hx_{0}=\sum_{t=0}^{\infty}x_{0}^{\top}L^{t}(F^{\top}RF+Q)x_{0}.$

An induction argument shows that this expression agrees with $v_{F}(x_{0})$ in
(29). This proves all claims in Lemma 10.4. ∎

Let $\mathcal{P}_{G}$ be the set of all $P\in\mathcal{P}$ such that $P$ is
positive definite and the $P$-minimal control is in $\Sigma$.

######  Lemma 10.5.

If $P\in\mathcal{P}_{G}$ and $F$ is $P$-minimal, then $F$ is $P$-greedy.

###### Proof.

Fix $P\in\mathcal{P}_{G}$ and let $F$ be $P$-minimal. Since $Fx$ is the
minimizer of (27) when $v(x)=x^{\top}Px$, we have $x^{\top}T_{F}\,Px\leqslant
x^{\top}T_{S}\,Px$ for all $x\in\mathbbm{R}^{k}$ and $S\in\Sigma$. This is
equivalent to $T_{S}\,P\preccurlyeq T_{F}\,P$ for every $S\in\Sigma$.
Moreover, by the definition of $\mathcal{P}_{G}$, the policy $F$ is in
$\Sigma$. Hence $F$ is $P$-greedy. ∎

In the present LQ setting, the ADP Bellman operator becomes
$TP=\bigvee_{S}T_{S}\,P$, where the supremum is over all $S\in\Sigma$.

######  Lemma 10.6.

$P\in\mathcal{P}_{G}$ satisfies $TP=P$ if and only if $P$ obeys the Riccati
equation.

###### Proof.

Fix $P\in\mathcal{P}_{G}$ and let $F$ be $P$-minimal. By Lemma 10.5, $F$ is
$P$-greedy, so $TP=T_{F}\,P$. Thus, $TP=P$ is equivalent to
$P=T_{F}\,P=F^{\top}RF+Q+(A+BF)^{\top}P(A+BF)$. Some calculations show that
this equation is equivalent to the Riccati equation (see, e.g., Bertsekas,
(2012), Section 3.1). ∎

We can now prove Theorem 10.3 via Theorem 10.1. To this end, suppose, as in
Theorem 10.3, that $(A,B)$ is controllable and $(A,C)$ is observable. We have
already shown that $(\mathbbm{P},\mathbbm{T})$ is a well-posed pre-ADP. In
addition, $(\mathbbm{P},\mathbbm{T})$ is downward stable because each
$T_{F}\in\mathbbm{T}$ is order-preserving and globally stable (see Lemma 8.1).
Moreover, under the stated conditions, there exists a unique positive definite
solution $P^{*}$ to the Riccati equation (30) and, in addition, the
$P^{*}$-minimal policy $F$ obeys $\rho(A+BF)<1$ (see, e.g., Bertsekas, (2012),
Prop. 3.1.1). Hence, by Lemma 10.6, the ADP Bellman operator $T$ has unique
fixed point $P^{*}$ in $\mathcal{P}_{G}$. Thus, all of the conditions in
Theorem 10.1 are verified.

To see how Theorem 10.1 implies (ii)–(iii) of Theorem 10.3, note that (ii)
follows from $TP^{*}=P^{*}$, or, equivalently,

$P^{*}=F^{\top}RF+Q+(A+BF)^{\top}P^{*}(A+BF)\;\text{ where }F\text{ is
$P^{*}$-minimal}.$

Regarding (iii), fix arbitrary $S\in\Sigma$ and let $P_{S}$ be the unique
fixed point of $T_{S}$. By Lemma 10.4, the lifetime value of $S$ obeys
$v_{S}(x)=x^{\top}P_{S}\,x$ for all $x\in\mathbbm{R}^{k}$. By Theorem 10.1 we
have $v_{S}\preccurlyeq v^{*}$, which is in turn equivalent to
$x^{\top}P^{*}\,x\leqslant x^{\top}P_{S}\,x$ for all $x$. Hence
$v^{*}(x)\leqslant v_{S}(x)$ for all $x$. At the same time, since $F$ is
$P^{*}$-greedy, we have $T_{F}P^{*}=TP^{*}=P^{*}$. Because $T_{F}$ has unique
fixed point $P_{F}$ in $\mathcal{P}$, this means that $P^{*}=P_{F}$. We
conclude that $v_{F}(x)=x^{\top}P_{F}x=x^{\top}P^{*}x=v^{*}(x)\leqslant
v_{S}(x)$ for all $x\in\mathbbm{R}^{k}$ and $S\in\Sigma$. Thus, $F$ is LQ-
optimal.

##  11\. Conclusion

The “completely abstract” dynamic programming framework constructed in this
paper represents dynamic programs as operators over partially ordered sets and
allows us to acquire a range of new optimality results that include many
existing results as special cases. We used these methods to study some
relatively sophisticated dynamic optimization problems with a number of
challenging features.

There remain many possible extensions to the applications treated here. For
example, in Section 9.2 we studied an expected value Bellman equation
generated by a discrete choice estimation problem that replaces a mathematical
expectation with a general certainty equivalent operator. Work by Lu et al.,
(2023) suggests that it is possible to provide a strong set of optimality
results with nonlinear aggregators in this setting. We leave this topic for
future research.

There are also many high-level extensions that could be built on the framework
provided in this paper. An example is average-cost optimality for dynamic
programs, which we have not considered. Another is continuous time models.
These topics are also deferred for future work.

## References

  * Alessandria et al., (2021) Alessandria, G., Arkolakis, C., and Ruhl, K. J. (2021).  Firm dynamics and trade.  Annual Review of Economics, 13:253–280.
  * Aliprantis and Border, (1999) Aliprantis, C. D. and Border, Kim, C. (1999).  Infinite dimensional analysis: a hitchhiker’s guide.  Springer-Verlag, New York, 2 edition.
  * Balbus et al., (2014) Balbus, Ł., Reffett, K., and Woźny, Ł. (2014).  A constructive study of markov equilibria in stochastic games with strategic complementarities.  Journal of Economic Theory, 150:815–840.
  * Balbus et al., (2018) Balbus, Ł., Reffett, K., and Woźny, Ł. (2018).  On uniqueness of time-consistent markov policies for quasi-hyperbolic consumers under uncertainty.  Journal of Economic Theory, 176:293–310.
  * Bäuerle and Jaśkiewicz, (2018) Bäuerle, N. and Jaśkiewicz, A. (2018).  Stochastic optimal growth model with risk sensitive preferences.  Journal of Economic Theory, 173:181–200.
  * Becker and Rincón-Zapatero, (2021) Becker, R. A. and Rincón-Zapatero, J. P. (2021).  Thompson aggregators, scott continuous koopmans operators, and least fixed point theory.  Mathematical Social Sciences, 112:84–97.
  * Bertsekas, (2012) Bertsekas, D. (2012).  Dynamic programming and optimal control: Volume I, volume 1.  Athena scientific.
  * Bertsekas, (2021) Bertsekas, D. (2021).  Rollout, policy iteration, and distributed reinforcement learning.  Athena Scientific.
  * Bertsekas, (1977) Bertsekas, D. P. (1977).  Monotone mappings with application in dynamic programming.  SIAM Journal on Control and Optimization, 15(3):438–464.
  * Bertsekas, (2017) Bertsekas, D. P. (2017).  Regular policies in abstract dynamic programming.  SIAM Journal on Optimization, 27(3):1694–1727.
  * Bertsekas, (2022) Bertsekas, D. P. (2022).  Abstract dynamic programming.  Athena Scientific, 3 edition.
  * Bloise et al., (2023) Bloise, G., Le Van, C., and Vailakis, Y. (2023).  Do not blame bellman: It is koopmans’ fault.  Econometrica, in press.
  * Borovička and Stachurski, (2021) Borovička, J. and Stachurski, J. (2021).  Stability of equilibrium asset pricing models: A necessary and sufficient condition.  Journal of Economic Theory, 193:105227.
  * Cagetti et al., (2002) Cagetti, M., Hansen, L. P., Sargent, T. J., and Williams, N. (2002).  Robustness and pricing with uncertain growth.  The Review of Financial Studies, 15(2):363–404.
  * Davey and Priestley, (2002) Davey, B. A. and Priestley, H. A. (2002).  Introduction to lattices and order.  Cambridge University Press.
  * de Castro and Galvao, (2019) de Castro, L. and Galvao, A. F. (2019).  Dynamic quantile models of rational behavior.  Econometrica, 87(6):1893–1939.
  * de Castro et al., (2022) de Castro, L., Galvao, A. F., and Nunes, D. (2022).  Dynamic economics with quantile preferences.  Available at SSRN 4108230.
  * Denardo, (1967) Denardo, E. V. (1967).  Contraction mappings in the theory underlying dynamic programming.  Siam Review, 9(2):165–177.
  * Epstein and Zin, (1989) Epstein, L. G. and Zin, S. E. (1989).  Risk aversion and the temporal behavior of consumption and asset returns: A theoretical framework.  Econometrica, 57(4):937–969.
  * Fedus et al., (2019) Fedus, W., Gelada, C., Bengio, Y., Bellemare, M. G., and Larochelle, H. (2019).  Hyperbolic discounting and learning over multiple horizons.
  * Fei et al., (2021) Fei, Y., Yang, Z., Chen, Y., and Wang, Z. (2021).  Exponential bellman equation and improved regret bounds for risk-sensitive reinforcement learning.  Advances in Neural Information Processing Systems, 34:20436–20446.
  * Gao et al., (2021) Gao, Y., Lui, K. Y. C., and Hernandez-Leal, P. (2021).  Robust risk-sensitive reinforcement learning agents for trading markets.  Technical report, arXiv preprint arXiv:2107.08083.
  * Goebel and Kirk, (1990) Goebel, K. and Kirk, W. A. (1990).  Topics in metric fixed point theory.  Number 28. Cambridge university press.
  * Hansen and Sargent, (1995) Hansen, L. P. and Sargent, T. J. (1995).  Discounted linear exponential quadratic gaussian control.  IEEE Transactions on Automatic control, 40(5):968–971.
  * Hansen and Sargent, (2011) Hansen, L. P. and Sargent, T. J. (2011).  Robustness.  Princeton university press.
  * Hansen and Scheinkman, (2012) Hansen, L. P. and Scheinkman, J. A. (2012).  Recursive utility in a Markov environment with stochastic growth.  Proceedings of the National Academy of Sciences, 109(30):11967–11972.
  * Hernández-Lerma and Lasserre, (2012) Hernández-Lerma, O. and Lasserre, J. B. (2012).  Discrete-time Markov control processes: basic optimality criteria, volume 30.  Springer Science & Business Media.
  * Hopenhayn and Prescott, (1992) Hopenhayn, H. A. and Prescott, E. C. (1992).  Stochastic monotonicity and stationary distributions for dynamic economies.  Econometrica, pages 1387–1406.
  * Jacobson, (1973) Jacobson, D. H. (1973).  Optimal stochastic linear systems with exponential performance criteria and their relation to deterministic differential games.  IEEE Transactions for Automatic Control, AC-18:1124–131.
  * Jovanovic, (1982) Jovanovic, B. (1982).  Selection and the evolution of industry.  Econometrica, pages 649–670.
  * Kamihigashi, (2014) Kamihigashi, T. (2014).  Elementary results on solutions to the bellman equation of dynamic programming: existence, uniqueness, and convergence.  Economic Theory, 56:251–273.
  * Klibanoff et al., (2009) Klibanoff, P., Marinacci, M., and Mukerji, S. (2009).  Recursive smooth ambiguity preferences.  Journal of Economic Theory, 144(3):930–976.
  * Kochenderfer et al., (2022) Kochenderfer, M. J., Wheeler, T. A., and Wray, K. H. (2022).  Algorithms for decision making.  The MIT Press.
  * Kristensen et al., (2021) Kristensen, D., Mogensen, P. K., Moon, J. M., and Schjerning, B. (2021).  Solving dynamic discrete choice models using smoothing and sieve methods.  Journal of Econometrics, 223(2):328–360.
  * Lu et al., (2023) Lu, J., Luo, Y., Saito, K., and Xin, Y. (2023).  Does harold zurcher have time separable preferences?  Technical report, North American Summer Meeting of the Econometric Society.
  * Ma and Stachurski, (2021) Ma, Q. and Stachurski, J. (2021).  Dynamic programming deconstructed: Transformations of the bellman equation and computational efficiency.  Operations Research, 69(5):1591–1607.
  * Ma et al., (2020) Ma, Q., Stachurski, J., and Toda, A. A. (2020).  The income fluctuation problem and the evolution of wealth.  Journal of Economic Theory, 187:105003.
  * Marinacci and Montrucchio, (2010) Marinacci, M. and Montrucchio, L. (2010).  Unique solutions for stochastic recursive utilities.  Journal of Economic Theory, 145(5):1776–1804.
  * Marinacci and Montrucchio, (2019) Marinacci, M. and Montrucchio, L. (2019).  Unique tarski fixed points.  Mathematics of Operations Research, 44(4):1174–1191.
  * Meyer-Nieberg, (2012) Meyer-Nieberg, P. (2012).  Banach lattices.  Springer Science & Business Media.
  * Mogensen, (2018) Mogensen, P. K. (2018).  Solving dynamic discrete choice models: Integrated or expected value function?  arXiv preprint arXiv:1801.03978.
  * Powell et al., (2012) Powell, W. B., Simao, H. P., and Bouzaiene-Ayari, B. (2012).  Approximate dynamic programming in transportation and logistics: a unified framework.  EURO Journal on Transportation and Logistics, 1(3):237–284.
  * Puterman, (2005) Puterman, M. L. (2005).  Markov decision processes: discrete stochastic dynamic programming.  Wiley Interscience.
  * Ren and Stachurski, (2021) Ren, G. and Stachurski, J. (2021).  Dynamic programming with value convexity.  Automatica, 130:109641.
  * Rust, (1987) Rust, J. (1987).  Optimal replacement of gmc bus engines: An empirical model of harold zurcher.  Econometrica, pages 999–1033.
  * Rust, (1994) Rust, J. (1994).  Structural estimation of markov decision processes.  Handbook of econometrics, 4:3081–3143.
  * Stachurski, (2022) Stachurski, J. (2022).  Economic dynamics: theory and computation.  MIT Press, 2 edition.
  * Stachurski and Zhang, (2021) Stachurski, J. and Zhang, J. (2021).  Dynamic programming with state-dependent discounting.  Journal of Economic Theory, 192:105190.
  * Sterk et al., (2021) Sterk, V., Sedláček, P., and Pugsley, B. (2021).  The nature of firm growth.  American Economic Review, 111(2):547–579.
  * Stokey and Lucas, (1989) Stokey, N. L. and Lucas, R. E. (1989).  Recursive methods in dynamic economics.  Harvard University Press.
  * Toda, (2019) Toda, A. A. (2019).  Wealth distribution with random discount factors.  Journal of Monetary Economics, 104:101–113.
  * Toda, (2021) Toda, A. A. (2021).  Perov’s contraction principle and dynamic programming with stochastic discounting.  Operations Research Letters, 49(5):815–819.
  * Toda, (2023) Toda, A. A. (2023).  Unbounded markov dynamic programming with weighted supremum norm perov contractions.
  * Whittle, (1981) Whittle, P. (1981).  Risk-sensitive linear/quadratic/gaussian control.  Advances in Applied Probability, 13(4):764–777.
  * Yu et al., (2023) Yu, L., Lin, L., Guan, G., and Liu, J. (2023).  Time-consistent lifetime portfolio selection under smooth ambiguity.  Mathematical Control and Related Fields, 13(3):967–987.
  * Zaanen, (2012) Zaanen, A. C. (2012).  Introduction to operator theory in Riesz spaces.  Springer.