Elementary results on solutions to the bellman equation of dynamic programming: existence, uniqueness, and convergence

Abstract

We establish some elementary results on solutions to the Bellman equation without introducing any topological assumption. Under a small number of conditions, we show that the Bellman equation has a unique solution in a certain set, that this solution is the value function, and that the value function can be computed by value iteration with an appropriate initial condition. In addition, we show that the value function can be computed by the same procedure under alternative conditions. We apply our results to two optimal growth models: one with a discontinuous production function and the other with “roughly increasing” returns.

1 Introduction

Dynamic programming has been one of the most fundamental tools in economic analysis, particularly since Stokey and Lucas (1989).¹ One of the limitations of Stokey and Lucas’ work and earlier studies was that models with unbounded returns were not fully addressed though such models are extremely common in economics. This has been a major issue in the subsequent economic literature on dynamic programming, and important contributions have been made by Alvarez and Stokey (1998), Durán (2000), Le Van and Morhaim (2002), Rinćon-Zapatero and Rodríguez-Palmero (2003); Rinćon-Zapatero and Rodríguez-Palmero (2007); Rinćon-Zapatero and Rodríguez-Palmero (2009), Martins-da-Rocha and Vailakis (2010), and Matkowski and Nowak (2011).

One thing common to the results established by these recent contributions is that they rely heavily on topological assumptions, such as the continuity of the return function and that of the feasibility correspondence. While these assumptions are completely standard in many models, there are important cases in which they clearly fail. For example, threshold effects are associated with discontinuous technologies (Azariadis and Drazen 1990); moreoever, discontinuities are a common feature of ecological phenomena (Muradian 2001; Nævdal 2003).² Even a well-behaved maximization problem that depends continuously on a parameter often results in discontinuities since parametric continuity of the objective function does not imply parametric continuity of the solution.³ Thus, in general, discontinuities are widespread in principal–agent models and game theoretic models (though such models are beyond the scope of this paper).⁴

The purpose of this paper is to establish some elementary results on solutions to the Bellman equation—or fixed points of the Bellman operator—without introducing any topological assumption. Such results not only apply to models with discontinuities but also disentangle basic properties of fixed points of the Bellman operator from topological assumptions. One might think that in our approach, topological assumptions would simply be replaced by alternative, more abstract assumptions, but that is certainly not the case. In fact, the conditions required for each formal result proved in this paper are all included in the statement of the result itself, and they are expressed mostly in terms of inequalities between functions. Therefore, our results are highly accessible to applied researchers as well as graduate students.

Our main results are twofold. First, given an order interval of functions that is mapped into itself by the Bellman operator, if the upper and lower boundaries of this order interval satisfy transversality-like conditions, then (a) the Bellman operator has a unique fixed point in the order interval; (b) this fixed point is the value function; and (c) the value function can be computed by value iteration starting from the lower boundary of the order interval. Second, if there exists a function that is mapped upward by the Bellman operator, and if this function is dominated by the value function and satisfies a transversality-like condition, then the value function can be computed by value iteration starting from this function.

To understand why such results can be shown without any topological assumption, note that most of the recent contributions except for Le Van and Morhaim (2002) are based on variants of the contraction mapping theorem. In this approach, the Bellman operator is shown to be some type of contraction, and a variant of the contraction mapping theorem is used to show that the Bellman operator has a unique fixed point in the space of continuous functions with a suitable topology. Then, this fixed point is shown to be the value function using standard arguments.

However, the technical conditions required for these results imply that any fixed point in the function space under consideration must be the value function. Since there is only one value function, it follows that the uniqueness of a fixed point can be guaranteed without using any variant of the contraction mapping theorem. The idea of our approach is to use the Knaster–Tarski fixed point theorem instead of a variant of the contraction mapping theorem and to impose a minimal set of assumptions required for the application of the Knaster–Tarski theorem. It turns out that this approach requires no topological assumption, yielding results that are considerably simpler than most existing results. We clarify this point by comparing one of our main results with the recent result developed by Rinćon-Zapatero and Rodríguez-Palmero (2003); Rinćon-Zapatero and Rodríguez-Palmero (2009) and Martins-da-Rocha and Vailakis (2010).

There is of course a downside to our approach, which offers only a minimal convergence result and directly establishes no property of the value function except that it lies in the given order interval. On the other hand, in most cases, our convergence result is sufficient for computing the value function, and it is also useful in establishing certain properties of the value function under additional conditions. We discuss the latter point in some detail in Sect. 3.2.

In some sense, this paper is intended to be a continuation of Section 4.1 of Stokey and Lucas (1989), in which several fundamental results on dynamic programming were developed without topological assumptions. Stokey and Lucas introduced topological assumptions in their subsequent analysis, but it is possible to continue further without introducing any topological assumption. Our results are also similar in spirit to those shown by Bertsekas and Shreve (1978, Chapter 5), who mainly used monotonicity arguments. Our results extend some of their results to cases in which the return function is unbounded both above and below. In Sects. 2 and 3, we offer detailed discussions of how our results relate to existing ones, including the relevant results of Stokey and Lucas (1989) and Bertsekas and Shreve (1978).

The rest of the paper is organized as follows. In the next section, we describe our framework and state our main results, which we prove in the Appendix. In Sect. 3, we demonstrate how they can be used to derive other useful results and discuss related results in the literature. In Sect. 4, we present three examples. The first two examples are optimal growth models with logarithmic utility: one having a discontinuous production function and the other having “roughly increasing” returns. The third example demonstrates that value iteration may fail to converge to the value function unless the initial function is chosen appropriately. In Sect. 5, we conclude the paper.

2 Main results

Let $X$ be a set, and $\Gamma$ be a nonempty-valued correspondence from $X$ to $X$. Let $D$ be the graph of $\Gamma$:

$$\begin{aligned} D = \{(x, y) \in X \times X : y \in \Gamma (x)\}. \end{aligned}$$

(2.1)

Let $u : D \rightarrow [-\infty , \infty )$. In the optimization problem introduced below, $X$ is the state space, $\Gamma$ is the feasibility correspondence, $u$ is the return function, and $D$ is the domain of $u$.

Let $\Pi$ and $\Pi (x_{0})$ denote the set of feasible paths and that of feasible paths from $x_{0}$, respectively:

$$\begin{aligned} \Pi&= \{\{x_{t}\}_{t=0}^{\infty } \in X^{\infty } : {\forall }t \in {{\mathbb {Z}}}_{+}, x_{t+1} \in \Gamma (x_{t}) \}, \end{aligned}$$

(2.2)

$$\begin{aligned} \Pi (x_{0})&= \{\{x_{t}\}_{t=1}^{\infty } \in X^{\infty } : \{x_{t}\}_{t=0}^{\infty } \in \Pi \}, \qquad x_{0} \in X. \end{aligned}$$

(2.3)

Let $\beta \ge 0$. Given $x_{0} \in X$, consider the following optimization problem:

$$\begin{aligned} \sup _{\{x_{t}\}_{t=1}^{\infty } \in \Pi (x_{0})} L_{T \uparrow \infty } \sum _{t=0}^{T} \beta ^{t} u(x_{t}, x_{t+1}), \end{aligned}$$

(2.4)

where $L\in \{{\underline{\lim }}, {\overline{\lim }}\}$ with ${\underline{\lim }}= \liminf$ and ${\overline{\lim }}= \limsup$. Since $u(x,y) < \infty$ for all $(x,y) \in D$, the objective function is well defined for any feasible path.

For $\{x_{t}\}_{t=0}^{\infty } \in \Pi$, we define

$$\begin{aligned} S(\{x_{t}\}_{t=0}^{\infty }) = L_{T \uparrow \infty } \sum _{t=0}^{\infty } \beta ^{t} u(x_{t}, x_{t+1}). \end{aligned}$$

(2.5)

The value function $v^{*} : X \rightarrow \overline{{{\mathbb {R}}}}$ is defined by

$$\begin{aligned} v^{*}(x_{0}) = \sup _{\{x_{t}\}_{t=1}^{\infty } \in \Pi (x_{0})} S(\{x_{t}\}_{t=0}^{\infty }), \qquad x_{0} \in X. \end{aligned}$$

(2.6)

Note that $v^{*}(x_{0})$ is unaffected if $\Pi (x_{0})$ is replaced by $\Pi ^{0}(x_{0})$,⁵ where

$$\begin{aligned} \Pi ^{0}&= \{\{x_{t}\}_{t=0}^{\infty } \in \Pi : S(\{x_{t}\}_{t=0}^{\infty }) > -\infty \}, \end{aligned}$$

(2.7)

$$\begin{aligned} \Pi ^{0}(x_{0})&= \{\{x_{t}\}_{t=1}^{\infty } \in \Pi (x_{0}) : \{x_{t}\}_{t=0}^{\infty } \in \Pi ^{0} \}, \qquad x_{0} \in X. \end{aligned}$$

(2.8)

Let $V$ be the set of functions from $X$ to $[-\infty , \infty )$. The Bellman operator $B$ on $V$ is defined by

$$\begin{aligned} (B v)(x) = \sup _{y \in \Gamma (x)} \{u(x,y) + \beta v(y)\}, \qquad x \in X, v \in V. \end{aligned}$$

(2.9)

Given $v \in V$, it need not be the case that $B v \in V$. A fixed point of $B$ is a function $v \in V$ such that $B v = v.$ It follows from Kamihigashi (2008, Theorem 2) that $v^{*}$ is a fixed point of $B$ provided that $v^{*} \in V$:

Lemma 2.1

If $v^{*} \in V$, then $v^{*}$ is a fixed point of $B$.

This is essentially the same result as Theorem 4.2 of Stokey and Lucas (1989). The difference is that Lemma 2.1 does not assume that $u(x,y) > -\infty$ for all $(x,y) \in D$; this assumption is often violated in applications. Instead, the lemma assumes that $v^{*} \in V$.

Let $v, w : X \rightarrow \overline{{{\mathbb {R}}}}$. The partial order $\le$ on the set of functions from $X$ to $\overline{{{\mathbb {R}}}}$ is defined in the usual way:

$$\begin{aligned} v \le w \quad \Longleftrightarrow \quad {\forall }x \in X, \; v(x) \le w(x). \end{aligned}$$

(2.10)

The partial order $\le$ on the set of functions from $D$ to $\overline{{{\mathbb {R}}}}$ is defined in the same way. It is immediate from (2.9) that $B$ is a monotone operator on $V$:

$$\begin{aligned} v \le w \in V \quad \Rightarrow \quad B v \le B w. \end{aligned}$$

(2.11)

If $v \le w$, we define the order interval $[v, w]$ by

$$\begin{aligned}{}[v, w] = \{f \in V : v \le f \le w\}. \end{aligned}$$

(2.12)

The order interval $[-\infty , w]$ means $[v,w]$ with $v = -\infty$; likewise, $[v, \infty ]$ means $[v, w]$ with $w = \infty$.⁶

Now, we are ready to state the main results of this paper, the proofs of which appear in the Appendix.

Theorem 2.1

Suppose that there exist $\underline{v}, \overline{v} \in V$ such that

$$\begin{aligned}&\underline{v} \le \overline{v}, \end{aligned}$$

(2.13)

$$\begin{aligned}&B \underline{v} \ge \underline{v}, \end{aligned}$$

(2.14)

$$\begin{aligned}&B \overline{v} \le \overline{v},\end{aligned}$$

(2.15)

$$\begin{aligned}&{\forall }\{x_{t}\}_{t=0}^{\infty } \in \Pi ^{0}, \quad {\underline{\lim }}_{t \uparrow \infty } \beta ^{t} \underline{v}(x_{t}) \ge 0, \end{aligned}$$

(2.16)

$$\begin{aligned}&{\forall }\{x_{t}\}_{t=0}^{\infty } \in \Pi , \quad {\overline{\lim }}_{t \uparrow \infty } \beta ^{t} \overline{v}(x_{t}) \le 0. \end{aligned}$$

(2.17)

Then the following conclusions hold:

• (a) The Bellman operator $B$ has a unique fixed point in $[\underline{v}, \overline{v}]$.

• (b) This fixed point is the value function $v^{*}$.

• (c) The increasing sequence $\{B^{n} \underline{v}\}_{n = 1}^{\infty }$ converges to $v^{*}$ pointwise.⁷

In conclusion (c) above, the sequence $\{B^{n} \underline{v}\}_{n=1}^{\infty }$ is increasing because we have $B^{n+1} \underline{v} \ge B^{n} \underline{v}$ for any $n \in {{\mathbb {N}}}$ by applying $B^{n}$ to both sides of (2.14). The next two results follow from intermediate steps in the proof of Theorem 2.1.

Proposition 2.1

Suppose that there exists $\overline{v} \in V$ satisfying (2.17) and

$$\begin{aligned} v^{*} \le \overline{v}. \end{aligned}$$

(2.18)

Then $v^{*}$ is the largest fixed point of $B$ in $[-\infty , \overline{v}]$.⁸

Theorem 2.2

Suppose that $v^{*} \in V$. Suppose further that there exists $\underline{v} \in V$ satisfying (2.14), (2.16), and

$$\begin{aligned} \underline{v} \le v^{*}. \end{aligned}$$

(2.19)

Then $v^{*}$ is the smallest fixed point of $B$ in $[\underline{v}, \infty ]$. Furthermore, the increasing sequence $\{B^{n} \underline{v}\}_{n=1}^{\infty }$ converges to $v^{*}$ pointwise.

Proposition 2.1 and the first conclusion of Theorem 2.2 can be shown by extending the proof of Stokey and Lucas (1989, Theorem 4.3) to our slightly more general setting (though we do not entirely follow this route). Their argument, which assumes the stronger version of (2.16) with $\Pi$ in place of $\Pi ^{0}$, in fact goes through even with the original version of (2.16). The idea of replacing $\Pi$ with $\Pi ^{0}$ is due to Le Van and Morhaim (2002). This replacement is important because even the value function $v^{*}$ almost never satisfies the stronger version of (2.16) if the return function is unbounded below. See Sect. 3.3 for related conditions used by Rinćon-Zapatero and Rodríguez-Palmero (2003) and Martins-da-Rocha and Vailakis (2010).⁹

To our knowledge, the second conclusion of Theorem 2.2 is new. If it is known a priori that $v^{*} \in [\underline{v}, \overline{v}]$, which implies both (2.18) and (2.19), then Theorem 2.1 follows directly from Proposition 2.1 and Theorem 2.2. But since it is not known a priori whether $v^{*}$ lies in $[\underline{v}, \overline{v}]$, the additional contribution of Theorem 2.1 is to show that $v^{*}$ indeed lies in $[\underline{v}, \overline{v}]$.

If there exist functions $\underline{v}, \overline{v} \in V$ satisfying (2.13)–(2.15), then the Bellman operator $B$ has a fixed point in $[\underline{v}, \overline{v}]$ by the Knaster–Tarski fixed point theorem (see the Appendix for a precise argument). However, this fixed point need not be the value function $v^{*}$. In fact, under (2.13)–(2.15), we do not even know whether $v^{*}$ lies in $V$. Even if it does, it still need not lie in $[\underline{v}, \overline{v}]$ though it is a fixed point of $B$ by Lemma 2.1.

Therefore, additional conditions are needed to ensure that $v^{*} \in [\underline{v}, \overline{v}]$. Conditions (2.16) and (2.17), which we called transversality-like conditions in the Introduction, serve this purpose, implying that any fixed point of $B$ in $[\underline{v}, \overline{v}]$ must be the value function $v^{*}$. Since we already know that $B$ has a fixed point in $[\underline{v}, \overline{v}]$, this fixed point must be the value function $v^{*}$, so that $v^{*}$ lies in $[\underline{v}, \overline{v}]$. The uniqueness of a fixed point of $B$ in $[\underline{v}, \overline{v}]$ follows from the fact that any fixed point in $[\underline{v}, \overline{v}]$ equals $v^{*}$. Rinćon-Zapatero and Rodríguez-Palmero (2003) offer several nontrivial, economically relevant examples satisfying stronger versions of (2.13)–(2.17).

If (2.16) and (2.17) are violated, then the Bellman operator $B$ can have multiple fixed points in $[\underline{v}, \overline{v}]$; see Kamihigashi (2013). It follows that conditions such as (2.16) and (2.17) are crucial to ensuring that $v^{*}$ is the only fixed point of $B$ in $[\underline{v}, \overline{v}]$.

Note that in conclusion (c) of Theorem 2.1, convergence to $v^{*}$ is guaranteed only from $\underline{v}$. Our argument for this convergence result is based on the simple observation that the limit of the increasing sequence $\{B^{n} \underline{v}\}_{n=1}^{\infty }$ is the supremum of the sequence. This allows us to interchange this supremum with another supremum (see (6.16)–(6.18)) to show that the limit is the value function $v^{*}$. The case of the decreasing sequence $\{B^{n} \overline{v}\}_{n=1}^{\infty }$, which also converges pointwise, is not symmetric since the $\sup$ and $\inf$ operators are in general not interchangeable. In Sect. 4.3, we construct an example satisfying (2.13)–(2.17) in which $\lim _{n \uparrow \infty } B^{n} \overline{v} \ne v^{*}$.¹⁰

Recall that the definition of the value function $v^{*}$ in (2.6) depends on the definition of $L$, which can be ${\underline{\lim }}$ or ${\overline{\lim }}$. Thus, there are in fact two value functions: one with $L= {\underline{\lim }}$ and the other with $L= {\overline{\lim }}$. An interesting implication of Theorem 2.1 is that these two functions coincide under (2.13)–(2.17). This is because the unique fixed point of $B$ established in Theorem 2.1 depends only on $B$, which is independent of $L$.

3 Corollaries

3.1 Special cases

In this subsection, we show various special cases of the results shown in the previous section to illustrate how our results can be used to derive other useful results. Many of the results shown here are more or less known, but these results are intended to clarify how our results relate to existing ones. The last two results in this subsection are new and useful in our view. Let us start with a simple consequence of Proposition 2.1.

Corrollary 3.1

Suppose that there exists $\overline{v} \in V$ satisfying (2.15), (2.17), and (2.18). Let $\overline{v}^{*}$ be the pointwise limit of the decreasing sequence $\{B^{n} \overline{v}\}_{n=1}^{\infty }$. Then $v^{*} \le \overline{v}^{*}.$ Furthermore, if $\overline{v}^{*}$ is a fixed point of $B$, then $\overline{v}^{*} = v^{*}$.

Proof

The inequality $v^{*} \le \overline{v}^{*}$ is immediate from (2.15) and (2.18). If $\overline{v}^{*}$ is a fixed point of $B$, then $\overline{v}^{*} \le v^{*}$ by Proposition 2.1; thus, $\overline{v}^{*} = v^{*}$.

The above result is essentially equivalent to Theorem 4.14 of Stokey and Lucas (1989). Corollary 3.1 along with Proposition 2.1 implies the following.

Corrollary 3.2

Suppose that $u \le 0$. Then $v^{*}$ is the largest negative fixed point of $B$. Let $\overline{v}^{*}$ be the pointwise limit of the decreasing sequence $\{B^{n} 0\}_{n=1}^{\infty }$. Then $v^{*} \le \overline{v}^{*}.$ Furthermore, if $\overline{v}^{*}$ is a fixed point of $B$, then $\overline{v}^{*} = v^{*}$.

Proof

Since $u \le 0$, we have $B 0 \le 0$ and $v^{*} \le 0$; thus, (2.15) and (2.18) hold with $\overline{v} = 0$. In addition, (2.17) trivially holds. Hence, the conclusions hold by Proposition 2.1 and Corollary 3.1.

The above result is essentially equivalent to Proposition 5.8 of Bertsekas and Shreve (1978). The following result deals with the case $u \ge 0$.

Corrollary 3.3

Suppose that $u \ge 0$, and that $v^{*} \in V$. Then $v^{*}$ is the smallest positive fixed point of $B$, and the increasing sequence $\{B^{n} 0\}_{n=1}^{\infty }$ converges to $v^{*}$ pointwise.

Proof

Since $u \ge 0$, we have $B 0 \ge 0$ and $v^{*} \ge 0$; thus (2.14) and (2.19) hold with $\underline{v} = 0$. In addition, (2.16) trivially hold. Hence the conclusions hold by Theorem 2.2.

The above result is essentially equivalent to Proposition 5.7 of Bertsekas and Shreve (1978). Corollaries 3.2 and 3.3 indicate that our results in the previous section extend their results to problems in which the return function is unbounded both above and below. Since such return functions are common in economics, this extension is significant. It is also nontrivial given that Bertsekas and Shreve’s (1978, Chapter 5) arguments rely heavily on the assumption that the return function takes only one sign, as assumed in Corollaries 3.2 and 3.3 above.

Next, we consider the case in which the return function $u$ is bounded:

Corrollary 3.4

Suppose that $\beta \in [0,1)$. Suppose further that there exist constants $\underline{\mu }, \overline{\mu } \in {{\mathbb {R}}}$ such that

$$\begin{aligned} \underline{\mu } \le u \le \overline{\mu }. \end{aligned}$$

(3.1)

Then conclusions (a)–(c) of Theorem 2.1 hold with

$$\begin{aligned} \underline{v} = \frac{\underline{\mu }}{1-\beta }, \qquad \overline{v} = \frac{\overline{\mu }}{1-\beta }. \end{aligned}$$

(3.2)

Proof

We have $\underline{v} \le \overline{v}$ by construction. Note that for any $x \in X$, we have

$$\begin{aligned} (B \underline{v})(x)&= \sup _{y \in \Gamma (x)} \{u(x,y) + \beta \underline{v}(y)\} \end{aligned}$$

(3.3)

$$\begin{aligned}&\ge \sup _{y \in \Gamma (y)} \{\underline{\mu } + \beta \underline{\mu }/(1-\beta )\} = \underline{\mu }/(1-\beta ) = \underline{v}(x). \end{aligned}$$

(3.4)

Thus, $B \underline{v} \ge \underline{v}$. We similarly obtain $B \overline{v} \le \overline{v}$. Hence, (2.13)–(2.15) hold. Since $\underline{v}$ and $\overline{v}$ are constant functions and $\beta \in [0,1)$, (2.16) and (2.17) trivially hold. Conclusions (a)–(c) of Theorem 2.1 now follow.

The above result is similar to the well-known result that if $u$ is bounded and continuous, and if $\Gamma$ is continuous and compact-valued, then the Bellman operator has a unique fixed point in the space of bounded continuous functions; this fixed point is the value function; and value iteration converges uniformly to the value function starting from any bounded continuous function (Stokey and Lucas 1989, pp. 79–80). Corollary 3.4 shows that similar conclusions can be obtained without any topological assumption except for the globally uniform convergence result. This result is particularly useful to applied researchers and graduate students because it can be shown and used without knowing mathematical concepts such as metric spaces, contractions, and completeness. In addition, even under standard topological assumptions, the approach based on the contraction mapping theorem fails as soon as one inequality is removed from (3.1), but our approach continues to work:

Corrollary 3.5

Suppose that $\beta \in [0,1)$, and that $v^{*} \in V$. Suppose further that there exists a constant $\underline{\mu } \in {{\mathbb {R}}}$ such that $u \ge \underline{\mu }$. Then $v^{*}$ is the smallest fixed point $v$ of $B$ with $v \ge \underline{\mu }/(1-\beta )$, and the increasing sequence $\{B^{n} \underline{\mu }\}_{n=1}^{\infty }$ converges to $v^{*}$ pointwise.

Proof

Let $\underline{v} = \underline{\mu }/(1-\beta ) \in V$. Then (2.14) and (2.16) hold as in the proof of Corollary 3.4. In addition, (2.19) is immediate from the inequality $u \ge \underline{\mu }$. Thus, the conclusions hold by Theorem 2.2.

The above result is similar to Corollary 3.3, but requires the additional assumption that $\beta \in [0,1)$ in order to allow for the case $\underline{\mu } < 0$. To our knowledge, the next two results are new although they are somewhat similar to Corollaries 3.4 and 3.5. The new results show how one can construct functions $\underline{v}$ and $\overline{v}$ that can be used to apply Theorems 2.1 and/or 2.2 even when the conditions of Corollaries 3.4 and 3.5 are too restrictive; see Sect. 4.1 for applications.

Corrollary 3.6

Suppose that there exist functions $\underline{u}, \overline{u} : D \rightarrow [-\infty , \infty )$ such that

$$\begin{aligned} \underline{u} \le u \le \overline{u}. \end{aligned}$$

(3.5)

Suppose further that there exist correspondences $\underline{\Gamma }, \overline{\Gamma } : X \rightarrow X$ such that

$$\begin{aligned} {\forall }x \in X, \quad \underline{\Gamma }(x) \subset \Gamma (x) \subset \overline{\Gamma }(x). \end{aligned}$$

(3.6)

Let $\underline{v} : X \rightarrow \overline{{{\mathbb {R}}}}$ be the value function given by (2.6) with $\underline{u}$ and $\underline{\Gamma }$ replacing $u$ and $\Gamma$, respectively. Let $\overline{v} : X \rightarrow \overline{{{\mathbb {R}}}}$ be the value function given by (2.6) with $\overline{u}$ and $\overline{\Gamma }$ replacing $u$ and $\Gamma$, repectively. Suppose that $\overline{v} \in V$, and that (2.16) and (2.17) hold. Then conclusions (a)–(c) of Theorem 2.1 hold.

Proof

We have $\underline{v} \le \overline{v}$ by construction. Since $\underline{v} \le \overline{v} \in V$, we have $\underline{v} \in V$ as well. Note that for any $x \in X$, we have

$$\begin{aligned} (B \underline{v})(x)&= \sup _{y \in \Gamma (x)} \{u(x,y) + \beta \underline{v}(y)\} \end{aligned}$$

(3.7)

$$\begin{aligned}&\ge \sup _{y \in \underline{\Gamma }(y)} \{\underline{u}(x,y) + \beta \underline{v}(y)\} = \underline{v}(x), \end{aligned}$$

(3.8)

where the last equality holds by Lemma 2.1. It follows that $B \underline{v} \ge \underline{v}$. We similarly obtain $B \overline{v} \le \overline{v}$. Now (2.13)–(2.15) hold. Since (2.16) and (2.17) hold by assumption, conclusions (a)–(c) of Theorem 2.1 now follow.

Corrollary 3.7

Suppose that $v^{*} \in V$, and that there exists a function $\underline{u} : D \rightarrow [-\infty , \infty )$ such that $\underline{u} \le u.$ Suppose further that there exists a correspondence $\underline{\Gamma } : X \rightarrow X$ such that $\underline{\Gamma }(x) \subset \Gamma (x)$ for all $x \in X$. Define $\underline{v}$ as in Corollary 3.6. Suppose that (2.16) holds. Then $v^{*}$ is the smallest fixed point $v$ of $B$ in $[\underline{v}, \infty ]$, and the increasing sequence $\{B^{n} \underline{v}\}_{n=1}^{\infty }$ converges to $v^{*}$ pointwise.

Proof

We have (2.14) and (2.16) as in the proof of Corollary 3.6. In addition, (2.19) is immediate from the inequality $\underline{u} \le u$. Since $v^{*} \in V$ by hypothesis, we have $\underline{v} \in V$ by (2.19). Thus, the conclusions hold by Theorem 2.2.

3.2 Properties of the value function

There are two obvious limitations of the convergence result in Theorems 2.1 and 2.2. First, convergence to the value function $v^{*}$ is guaranteed only from one particular function $\underline{v}$. Second, convergence occurs only pointwise. Despite these limitations, there are various situations in which this convergence result can help establish a property of the value function. This is because pointwise convergence preserves many important properties such as monotonicity, concavity, convexity, measurability, and supermodularity. In fact, any property that can be expressed in terms of weak inequalities is preserved under pointwise convergence. In addition, since our convergence result deals only with a particular increasing sequence starting from $\underline{v}$, it suffices to verify that a property of interest is preserved at the limit of this sequence. The following result formalizes this idea.

Corrollary 3.8

Suppose that $v^{*} \in V$. Let $\underline{v} \in V$ satisfy (2.14), (2.16), and (2.19). Let $W \subset V$ satisfy the following conditions:

• (i) $\underline{v} \in W$.

• (ii) For any $v \in W$ with $B v \ge v$, we have $B v \in W$.

• (iii) For any increasing sequence $\{v_{n}\}_{n=1}^{\infty } \subset W$ with $\lim _{n \uparrow \infty } v_{n} \in V$, we have $\lim _{n \uparrow \infty } v_{n} \in W$.

Then $v^{*} \in W$.

Proof

Let $\underline{v}$ and $W$ be as above. For $n \in {{\mathbb {N}}}$, let $\underline{v}_{n} = B^{n} \underline{v}$, and let $\underline{v}^{*} = \lim _{n \uparrow \infty } \underline{v}_{n}$. By Theorem 2.2, we have $\underline{v}^{*} = v^{*}$. Since $\underline{v} \in W$ by condition (i), and since the sequence $\{B^{n} \underline{v}\}$ is increasing by (2.14), we have $\underline{v}_{n} \in W$ for all $n \in {{\mathbb {N}}}$ by condition (ii). By condition (iii), we have $\underline{v}^{*} \in W$; that is, $v^{*} \in W$.

To see how the above result can be used in practice, suppose that one wishes to establish that the value function has a certain property, say property (P). One can do so in four steps as follows:

• I. Find a function $\underline{v} \in V$ with property (P) that satisfies (2.14), (2.16), and (2.19).

• II. Show that if a function $v \in V$ has property (P) and satisfies $B v \ge v$, then $B v$ also has property (P).

• III. Show that for any increasing sequence $\{v_{n}\}$ such that each $v_{n}$ has property (P), $\lim _{n \uparrow \infty } v_{n}$ also has property (P).

• IV. Using Corollary 3.8, conclude that the value function $v^{*}$ has property (P).

This type of argument is not new (e.g., Stokey and Lucas 1989, p. 52; Amir et al. 1991, p. 637), but note that it is the convergence result in Theorems 2.1 and 2.2 that makes the above procedure work. In Sect. 4.2, we apply a slightly different version of this procedure to an optimal growth model with “roughly increasing” returns.

3.3 Comparison with the result shown by Rincón-Zapatero and Rodríguez-Palmero/Martins-da-Rocha and Vailakis

We now compare Theorem 2.1 with Martins-da-Rocha and Vailakis’ (2010, Sec. 3) result on the Bellman operator, which is built upon the work of Rinćon-Zapatero and Rodríguez-Palmero (2003); Rinćon-Zapatero and Rodríguez-Palmero (2009). Under numerous technical conditions, their result shows that the Bellman operator has a unique fixed point in a certain set of continuous functions, that this fixed point is the value function, and that value iteration converges locally uniformly to the value function starting from any continuous function in the given function set. Since our result does not establish any property of the value function and ensures only pointwise convergence from a specific initial function, the conclusions of our result are weaker in some directions. However, our result, which requires only a small subset of the conditions required by their result, is considerably simpler to apply. This point immediately becomes clear in what follows.

The result stated by Martins-da-Rocha and Vailakis (2010, Theorem 3.1) requires the assumptions listed below:

DP0. (i) $X = {{\mathbb {R}}}_{+}^{m}$ for some $m \in {{\mathbb {N}}}$. (ii) $\beta \in (0,1)$. (iii) The right-hand side of (2.5) with $L= \lim$ exists in $\overline{{{\mathbb {R}}}}$ for all $\{x_{t}\}_{t=0}^{\infty } \in \Pi$.

DP1. The feasibility correspondence $\Gamma$ is continuous and compact-valued.

DP2. The return function $u$ is continuous on $D$.

Let $C(X, [-\infty , \infty ))$ be the set of continuous functions from $X$ to $[-\infty , \infty )$. Under DP0(i), we define

$$\begin{aligned} X^{*}&= X {\setminus } \{0\}, \end{aligned}$$

(3.9)

$$\begin{aligned} C^{*}(X)&= \{v \in C(X, [-\infty , \infty )): {\forall }x \in X^{*}, v(x) > -\infty \}. \end{aligned}$$

(3.10)

Although DP2 requires $u$ to be continuous, it is allowed that $u(x,y) = -\infty$ for some $(x,y) \in D$. The following assumption requires that one can avoid $u(x,y) = -\infty$ unless $x = 0$.

DP3. There exists a continuous function $q : X^{*} \rightarrow X^{*}$ such that

$$\begin{aligned} {\forall }x \in X^{*}, \qquad (x, q(x)) \in D, \quad u(x, q(x)) > -\infty . \end{aligned}$$

(3.11)

DP4. (i) There exist $\underline{v}, \overline{v} \in C^{*}(X)$ satisfying (2.13)–(2.15). (ii) We have

$$\begin{aligned} {\forall }\{x_{t}\}_{t=0}^{\infty } \in \Pi ^{0}, \quad \lim _{t \uparrow \infty } \beta ^{t} \underline{v}(x_{t})&= 0, \end{aligned}$$

(3.12)

$$\begin{aligned} {\forall }\{x_{t}\}_{t=0}^{\infty } \in \Pi ^{0}, \quad \lim _{t \uparrow \infty } \beta ^{t} \overline{v}(x_{t})&= 0. \end{aligned}$$

(3.13)

(iii) For any $x_{0} \in X^{*}$, $\Pi ^{0}(x_{0}) \ne \emptyset$. (iv) There exists $\hat{v} \in C^{*}(X)$ such that

$$\begin{aligned} {\forall }x \in X^{*},&{\quad } \overline{v}(x) < \hat{v}(x), \quad (B \hat{v})(x) < \hat{v}(x), \end{aligned}$$

(3.14)

$$\begin{aligned} {\exists }\epsilon > 0,&{\quad } \sup _{x \in X^{*}: \Vert x\Vert < \epsilon } \frac{\underline{v}(x) - \hat{v}(x)}{\overline{v}(x) - \hat{v}(x)} < \infty , \end{aligned}$$

(3.15)

$$\begin{aligned} {\exists }\delta > 0,&{\quad } \sup _{x \in X^{*}: \Vert x\Vert < \delta } \frac{\overline{v}(x) - \hat{v}(x)}{(B \hat{v})(x) - \hat{v}(x)} < \infty , \end{aligned}$$

(3.16)

where $\Vert \cdot \Vert$ is any norm on ${{\mathbb {R}}}^{m}$.

DP5. There exists an increasing sequence $\{K_{j}\}_{j=1}^{\infty }$ of compact subsets of $X$ such that $\Gamma (K_{j}) \subset K_{j}$ for each $j \in {{\mathbb {N}}}$, and such that for any compact set $K \subset X$, there exists $j \in {{\mathbb {N}}}$ with $K \subset K_{j}$.

We are now ready to present the result stated by Martins-da-Rocha and Vailakis (2010):

Theorem 3.1

(Martins-da-Rocha and Vailakis 2010, Theorem 3.1) Under DP0–DP5, the following conclusions hold:

• (a) The Bellman operator $B$ has a unique fixed point in $[\underline{v}, \overline{v}] \cap C^{*}(X)$.

• (b) The unique fixed point of $B$ in $[\underline{v}, \overline{v}] \cap C^{*}(X)$ is the value function $v^{*}$.

• (c) For any $v \in [\underline{v}, \overline{v}] \cap C^{*}(X)$, the sequence $\{B^{n} v\}_{n=1}^{\infty }$ converges to $v^{*}$ in the topology generated by the family $\{d_{j}\}_{j=1}^{\infty }$ of semidistances defined for all $f, g \in [\underline{v}, \overline{v}] \cap C^{*}(X)$ by

  $$\begin{aligned} d_{j}(f, g) = \sup _{x \in K_{j} {\setminus } \{0\}} \left| \ln \frac{f(x) - \hat{v}(x)}{\overline{v}(x) - \hat{v}(x)} - \ln \frac{g(x) - \hat{v}(x)}{\overline{v}(x) - \hat{v}(x)} \right| , \quad j \in {{\mathbb {N}}}. \end{aligned}$$

  (3.17)

Let us compare the conclusions of Theorem 2.1 with those of Theorem 3.1 under DP0–DP5 (which imply the hypotheses of Theorem 2.1 by Corollary 3.9 below). In terms of the existence of a fixed point, Theorem 2.1 is weaker than Theorem 3.1 in the sense that the latter shows that the fixed point lies in $C^{*}(X)$ (and thus the value function $v^{*}$ is continuous). In terms of uniqueness, Theorem 2.1 is stronger than Theorem 3.1, which ensures uniqueness only in $[\underline{v}, \overline{v}] \cap C^{*}(X)$. In terms of convergence, Theorem 2.1 is considerably weaker than Theorem 3.1, which shows that convergence to $v^{*}$ occurs from any initial function in $[\underline{v}, \overline{v}] \cap C^{*}(X)$ under a criterion much stronger than ours.

Let us now clarify which parts of DP0–DP5 are needed for the conclusions of Theorem 2.1. The following is a corollary of Theorem 2.1.

Corrollary 3.9

Assume DP0(i), DP0(ii), DP4(i), (3.12), and DP5. Then the functions $\underline{v}$ and $\overline{v}$ given by DP4(i) satisfy (2.13)–(2.17), and thus conclusions (a)–(c) of Theorem 2.1 hold.

Proof

DP4(i) ensures (2.13)–(2.15). Condition (3.12) implies (2.16). To verify (2.17), let $\{x_{t}\}_{t=0}^{\infty } \in \Pi$. By DP5, there exists a compact set $K_{j}$ with $j \in {{\mathbb {N}}}$ such that $x_{0} \in K_{j}$ and $\Gamma (K_{j}) \subset K_{j}$. Since $\overline{v}$ is continuous by DP4(i), we have $\overline{v}(x_{t}) \le \max _{x \in K_{j}} \overline{v}(x) < \infty$ for all $t \in {{\mathbb {Z}}}_{+}$, which together with DP0(ii) implies (2.17).

The above result shows that a small subset of the conditions stated in DP0–DP5 is sufficient to show that the value function $v^{*}$ is the unique fixed point of the Bellman operator $B$ in $[\underline{v}, \overline{v}]$ and that convergence to $v^{*}$ occurs from $\underline{v}$. In the proof, (2.17) is shown as a consequence of DP5 rather than (3.13). The only role of DP0(i) is to keep $C^{*}(X)$ well defined, while that of DP5 is to ensure (2.17). Thus, DP0(i) can be dropped entirely if we do not require $\underline{v}, \overline{v} \in C^{*}(X)$, while DP5 can be replaced by a weaker sufficient condition for (2.17). The following result can be shown by modifying the proof of Corollary 3.9.

Corrollary 3.10

Let $\beta \in [0,1)$. Suppose that there exist $\underline{v}, \overline{v} \in V$ satisfying (2.13)–(2.16). Suppose further that for any $x \in X$, there exists a set $K \subset X$ such that $\Gamma (K) \subset K$ and $\sup _{x \in K} \overline{v}(x) < \infty$. Then conclusions (a)–(c) of Theorem 2.1 hold.

4 Examples

Throughout this section, we assume that $\beta \in (0,1)$ for simplicity.

4.1 Optimal growth with threshold effects

Azariadis and Drazen (1990, p. 508) define threshold effects as “radical differences in dynamic behavior arising from local variations in social returns to scale” and explain this idea by using a discontinuous production function. In this subsection, we consider a one-sector growth model with this feature. The example here is a special case of the model studied by Kamihigashi and Roy (2007).

Let $\underline{\theta }, \overline{\theta }, \hat{x} > 0$ with $\underline{\theta } < \overline{\theta }$. Consider the production function $f : {{\mathbb {R}}}_{+} \rightarrow {{\mathbb {R}}}$ specified by

$$\begin{aligned} f(x) = {\left\{ \begin{array}{ll} \underline{\theta } x &{} \text {if } x < \hat{x},\\ \overline{\theta } x &{} \text {if } x \ge \hat{x}. \end{array}\right. } \end{aligned}$$

(4.1)

Figure 1 illustrates a production function of this form. We define

$$\begin{aligned} u(x,y)&= \ln [f(x) - y], \quad (x,y) \in D, \end{aligned}$$

(4.2)

$$\begin{aligned} \Gamma (x)&= \{y \in {{\mathbb {R}}}: 0 \le y \le f(x)\}, \quad x \in X. \end{aligned}$$

(4.3)

This is clearly a special case of the framework described in Sect. 2.

Since the production function $f$ is discontinuous, it is immediately clear that $u$ is not a continuous function and $\Gamma$ is not a continuous correspondence.¹¹ Hence, any result that requires $u$ and $\Gamma$ to be continuous is not applicable here. For example, it is easy to see that this example violates DP1 and DP2 in Sect. 3.3. It also violates DP5, which rules out unbounded growth.

Fig. 1

Production function of the form (4.1)

In contrast, our results are easily applicable. To be specific, define

$$\begin{aligned} \underline{u}(x,y) = \ln (\underline{\theta } x - y), \quad \overline{u}(x,y) = \ln (\overline{\theta } x - y), \end{aligned}$$

(4.4)

$$\begin{aligned} \underline{\Gamma }(x) = \{y \in {{\mathbb {R}}}: 0 \le y \le \underline{\theta } x\}, \quad \overline{\Gamma }(x) = \{y \in {{\mathbb {R}}}: 0 \le y \le \overline{\theta } x\}. \end{aligned}$$

(4.5)

Let $\underline{B}$ and $\overline{B}$ be the Bellman operators corresponding to $(\underline{u}, \underline{\Gamma })$ and $(\overline{u}, \overline{\Gamma })$, respectively. Then, using the method of undetermined coefficients, it is easy to show that there exist $\underline{\gamma }, \overline{\gamma }, \underline{\eta }, \overline{\eta } > 0$ such that $\underline{v} = \underline{B}\, \underline{v}$ and $\overline{v} = \overline{B} \overline{v}$ with

$$\begin{aligned} \underline{v}(x) = \underline{\gamma } \ln x + \underline{\eta }, \quad \overline{v}(x) = \overline{\gamma } \ln x + \overline{\eta }. \end{aligned}$$

(4.6)

In particular,

$$\begin{aligned} \underline{\gamma } = \overline{\gamma } = \frac{1}{1-\beta }, \quad \underline{\eta } = \frac{1}{(1-\beta )^{2}}[\ln \underline{\theta } + \beta \ln \beta + (1-\beta ) \ln (1-\beta )], \end{aligned}$$

(4.7)

and $\overline{\eta }$ is similar.¹² It is easy to see that (2.13)–(2.15) hold. It is also easy to verify (2.16) and (2.17) following Rinćon-Zapatero and Rodríguez-Palmero (2003, Example 12); thus, conclusions (a)–(c) of Theorem 2.1 hold.

Note that in the above argument, it was not required to show that $\underline{v}$ and $\overline{v}$ are the value functions corresponding to $(\underline{u}, \underline{\Gamma })$ and $(\overline{u}, \overline{\Gamma })$, respectively. However, one can easily show that $\underline{v}$ and $\overline{v}$ are indeed the associated value functions by using Theorem 2.1 or Corollary 3.1.¹³ In that case, one can apply Corollary 3.6 or 3.7 to obtain the corresponding conclusions.

In this example, the production function is assumed to have only one discontinuity and to be upper semicontinuous. However, these properties are not required by our results. Indeed, the above arguments go through as long as the production function lies between $\underline{\theta } x$ and $\overline{\theta } x$.

4.2 Optimal growth with roughly increasing returns

The importance of increasing returns in explaining cross-country differences in the long run has been well recognized since Romer (1986). In this subsection, we consider an optimal growth model with “roughly increasing” returns, which is again a special case of the model studied by Kamihigashi and Roy (2007). In particular, we assume that the production function $f$ is continuous and strictly increasing, and that there exist $\underline{\theta }, \overline{\theta } \in {{\mathbb {R}}}_{++}$ and $\alpha \in (1,1/\beta )$ such that

$$\begin{aligned} \underline{\theta } x^{\alpha } \le f(x) \le \overline{\theta } x^{\alpha }. \end{aligned}$$

(4.8)

Figure 2 illustrates a production function of this form, which roughly exhibits increasing returns. We define the return function $u$ and the feasibility correspondence $\Gamma$ by (4.2).

Fig. 2

Production function of the form (4.8)

In this example, both $u$ and $\Gamma$ are continuous, but to our knowledge, in the current literature, there is no result on the convergence of value iteration that applies to this example. However, our results are easily applicable as in the previous subsection. To demonstrate this, define $\underline{u}, \underline{\Gamma }, \overline{u}$, and $\overline{\Gamma }$ by (4.4) and (4.5) with $\underline{\theta } x^{\alpha }$ and $\overline{\theta } x^{\alpha }$ replacing $\underline{\theta } x$ and $\overline{\theta } x$, respectively. Then following the procedure in the previous subsection, we see that there exist $\underline{\gamma }, \overline{\gamma }, \underline{\eta }, \overline{\eta } > 0$ such that $\underline{v} = \underline{B}\, \underline{v}$ and $\overline{v} = \overline{B} \overline{v}$ with $\underline{v}$ and $\overline{v}$ given by (4.6); thus, we can apply Theorem 2.1 in the same way. In particular, the increasing sequence $\{B^{n} \underline{v}\}$ converges to $v^{*}$ pointwise.

It follows from Kamihigashi and Roy (2007, Lemma 3.3) that the value function $v^{*}$ here is upper semicontinuous. Let us show that $v^{*}$ is in fact continuous.¹⁴ Since $\underline{v}$ is continuous, and since the Bellman operator $B$ here maps a continuous function to another continuous function, $B^{n} \underline{v}$ is continuous for each $n \in {{\mathbb {N}}}$. However, we cannot apply Corollary 3.8 here since continuity is not preserved under pointwise convergence. On the other hand, the pointwise limit of an increasing sequence of continuous functions is lower semicontinuous (e.g., Aliprantis and Border 2006, Lemma 2.41). This suffices for our purpose since then $v^{*}$ is both upper and lower semicontinuous, i.e., $v^{*}$ is continuous.

4.3 Nonconvergence of $\{B^{n} \overline{v}\}$ to $v^{*}$

Under (2.13)–(2.17), conclusion (c) of Theorem 2.1 shows that the increasing sequence $\{B^{n} \underline{v}\}_{n=1}^{\infty }$ converges to the value function $v^{*}$ pointwise. The natural question is as follows: Does the decreasing sequence $\{B^{n} \overline{v}\}_{n=1}^{\infty }$ also converge to $v^{*}$? The answer is no in general.

To verify this, let $\alpha \in (0,\beta )$. Consider the symbolic diagram depicted in Fig. 3; more precisely, assume the following:

$$\begin{aligned} X&= \{(i,j) : i, j \in {{\mathbb {Z}}}_{+}, j \le i\}, \end{aligned}$$

(4.9)

$$\begin{aligned} \Gamma ((i,j))&= {\left\{ \begin{array}{ll} \{(i', 0) : i' \in {{\mathbb {Z}}}_{+}\} &{} \text {if }(i,j) = (0,0), \\ \{(i, j)\} &{} \text {if }i = j \ne 0, \\ \{(i, j+1)\} &{} \text {if }j < i, \end{array}\right. } \end{aligned}$$

(4.10)

$$\begin{aligned} u((i,j), (i', j'))&= {\left\{ \begin{array}{ll} - \alpha &{} \text {if }(i,j) = (i',j') = (0,0), \\ -\beta ^{-i} &{} \text {if }(i,j) = (i',j') \ne (0,0), \\ 0 &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

(4.11)

The value function $v^{*}$ can be computed directly:¹⁵

$$\begin{aligned} v^{*}((i,j)) = {\left\{ \begin{array}{ll} -\alpha /(1-\beta ) &{} \text {if }(i,j) = (0,0), \\ -\beta ^{-j}/(1-\beta ) &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

(4.12)

Fig. 3

States $(i,j) \in X$ (circles), feasible transitions (arrows), and associated returns (values adjacent to arrows) under (4.9)–(4.11)

Let $\underline{v} = v^{*}$ and $\overline{v} = 0$. Then $\underline{v} \le \overline{v}$ and $B \underline{v} = \underline{v}$. Since $u \le 0$, we have $B \overline{v} \le \overline{v}$. Thus (2.13)–(2.15) hold. As any feasible path eventually becomes constant, (2.16) and (2.17) hold with equality. Hence, Theorem 2.1 applies.

Consider the decreasing sequence $\{\overline{v}_{n}\}_{n=1}^{\infty } \equiv \{B^{n} \overline{v}\}_{n=1}^{\infty }$. If $(i,j) \ne (0,0)$, there is only one feasible transition from $(i,j)$, so that $\overline{v}_{n}((i,j))$ can be computed directly:

$$\begin{aligned} \overline{v}_{n}((i,j)) = {\left\{ \begin{array}{ll} -\beta ^{-j} \sum _{k=0}^{n-(i-j)-1} \beta ^{k} &{} \text {if }i > 0\hbox { and }n \ge i-j+1, \\ 0 &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

(4.13)

This formula works for $(i,j) = (0,0)$ as well; that is, $\overline{v}_{n}((0,0)) = 0$ for all $n \in {{\mathbb {N}}}$.¹⁶

Now letting $\overline{v}^{*} = \lim _{n \uparrow \infty } \overline{v}_{n}$, we see that $\overline{v}^{*}((i,j)) = v^{*}((i,j))$ for all $(i,j) \in X{\setminus }\{(0,0)\}$, but $\overline{v}^{*}((0,0)) = 0 > v^{*}((0,0))$; i.e., the sequence $\{\overline{v}_{n}\}_{n=1}^{\infty }$ fails to converge to $v^{*}$ at $(0,0)$.

Interestingly, the sequence $\{B^{n} \overline{v}^{*}\}_{t=1}^{\infty }$ restarted from $\overline{v}^{*}$ converges to $v^{*}$. Indeed, $(B^{n} \overline{v}^{*})((0,0)) = -\alpha (1 + \beta + \cdots + \beta ^{n-1}) \rightarrow v^{*}((0,0))$ as $n \uparrow \infty$.

5 Concluding remarks

In this paper, we have established some elementary results on solutions to the Bellman equation—or fixed points of the Bellman operator—without introducing any topological assumption. Our main results are twofold. First, given an order interval of functions that is mapped into itself by the Bellman operator, if the upper and lower boundaries of the order interval satisfy transversality-like conditions, then (a) the Bellman equation has a unique solution in this order interval, (b) this solution is the value function, and (c) the value function can be computed by value iteration starting from the lower boundary of the order interval. Second, if there exists a function that is mapped upward by the Bellman operator, and if this function is dominated by the value function and satisfies a transversality-like condition, then the value function can be computed by value iteration starting from this function. As a consequence of these results, we have derived various known results to clarify how our results relate to existing ones. We have applied our results to two optimal growth models, one with a discontinuous production function and the other with “roughly increasing” returns. We have also presented an example to show that even under the conditions of our first main result, value iteration starting from the upper boundary of the order interval need not converge to the value function.

Our results are elementary in the sense that they do not require any knowledge of mathematics beyond undergraduate analysis. Therefore, they are highly accessible to applied researchers as well as graduate students. Even in situations where standard topological assumptions hold, our results are considerably simpler than most of the existing results on fixed points of the Bellman operator. In addition, our results, which require no topological assumption, apply to models with discontinuities and even to those with “roughly increasing” returns.

In sharp contrast to the existing results based on variants of the contraction mapping theorem, our results directly establish virtually no property of the value function. Regarding this matter, we have shown how the increasing, convergent sequence given by our results can be used to derive certain properties of the value function. We plan to pursue applications of this idea as well as extensions to stochastic models in future research.

Appendix: Proofs

1.1 Proof of Theorem 2.1

The proof consists of three lemmas and a concluding argument. The proof of the first lemma slightly generalizes an argument of Stokey and Lucas (1989, Theorem 4.3). The second lemma essentially shows that $B^{T} v$ with $T \in {{\mathbb {N}}}$ and $v \in V$ is the value function of the $T$-period problem with the value of the terminal stock $x_{T}$ given by $v(x_{T})$. This result extends the classical idea of Bertsekas and Shreve (1978, Section 3.2) to our setting. The last lemma is less trivial than the first two. The concluding argument applies the Knaster–Tarski fixed point theorem and combines the first and last lemmas.

Lemma 6.1

Let $\overline{v} \in V$ satisfy (2.17). Let $v \in V$ be a fixed point of $B$ with $v \le \overline{v}$. Then $v \le v^{*}$.

Proof

Let $x_{0} \in X$. If $v(x_{0}) = -\infty$, then $v(x_{0}) \le v^{*}(x_{0})$. Consider the case $v(x_{0}) > -\infty .$ Let $\epsilon > 0$. Let $\{\epsilon _{t}\}_{t=0}^{\infty } \subset (0,\infty )$ be such that $\sum _{t=0}^{\infty } \beta ^{t} \epsilon _{t} \le \epsilon .$ Since $v = B v$, for any $t \in {{\mathbb {Z}}}_{+}$ and $x_{t} \in X$, there exists $x_{t+1} \in \Gamma (x_{t})$ such that

$$\begin{aligned} v(x_{t}) \le u(x_{t}, x_{t+1}) + \beta v(x_{t+1}) + \epsilon _{t}. \end{aligned}$$

(6.1)

We pick $x_{1} \in \Gamma (x_{0}), x_{2} \in \Gamma (x_{1}), \ldots$ so that (6.1) holds for all $t \in {{\mathbb {Z}}}_{+}$. Then $\{x_{t}\}_{t=1}^{\infty } \in \Pi (x_{0})$. By repeated application of (6.1), we have

$$\begin{aligned} v(x_{0})&\le u(x_{0}, x_{1}) + \beta v(x_{1}) + \epsilon _{0} \end{aligned}$$

(6.2)

$$\begin{aligned}&\le u(x_{0}, x_{1}) + \beta [u(x_{1}, x_{2}) + \beta v(x_{2}) + \epsilon _{1}] + \epsilon _{0} \end{aligned}$$

(6.3)

$$\begin{aligned}&\quad \vdots \end{aligned}$$

(6.4)

$$\begin{aligned}&\le \sum _{t=0}^{T-1} \beta ^{t} u(x_{t}, x_{t+1}) + \beta ^{T} v(x_{T}) + \epsilon , \quad {\forall }T \in {{\mathbb {N}}}. \end{aligned}$$

(6.5)

Since $v(x_{0}) > -\infty$, we have $\beta ^{T} v(x_{T}) > -\infty$ for all $T \in {{\mathbb {N}}}$. It follows that

$$\begin{aligned} v(x_{0}) - \epsilon - \beta ^{T} v(x_{T}) \le \sum _{t=0}^{T-1} \beta ^{t} u(x_{t}, x_{t+1}). \end{aligned}$$

(6.6)

Applying ${\underline{\lim }}_{T \uparrow \infty }$ to both sides and recalling (2.5) and (2.6), we have

$$\begin{aligned} v(x_{0}) - \epsilon - {\overline{\lim }}_{T \uparrow \infty } \beta ^{T} v(x_{T}) \le {\underline{\lim }}_{T \uparrow \infty } \sum _{t=0}^{T-1} \beta ^{t} u(x_{t}, x_{t+1}) \le S(\{x_{t}\}_{t=0}^{\infty }) \le v^{*}(x_{0}). \end{aligned}$$

(6.7)

By (2.17), we have $v(x_{0}) - \epsilon \le v^{*}(x_{0})$. Since this is true for any $\epsilon > 0$, we have $v(x_{0}) \le v^{*}(x_{0})$. Since $x_{0}$ is arbitrary, we obtain $v \le v^{*}$. $\square$

For any $v \in V$, define $v_{1} = B v$; for each $n \in {{\mathbb {N}}}$, provided that $v_{n} \in V$, define $v_{n+1} = B v_{n}$. The following remark follows from (2.11).

Remark 6.1

Let $v, w \in V$ satisfy $v \le w$ and $B w \le w$. Then for all $n \in {{\mathbb {N}}}$, we have $v_{n} \le w$ and thus $v_{n} \in V$.

Lemma 6.2

Let $\overline{v} \in V$ satisfy (2.15). Let $v \in V$ satisfy $v \le \overline{v}$. Then for any $T \in {{\mathbb {N}}}$, we have $v_{T} \in V$ and

$$\begin{aligned} {\forall }x_{0} \in X, \quad v_{T}(x_{0}) = \sup _{\{x_{t}\}_{t=1}^{\infty } \in \Pi (x_{0})} \left\{ \sum _{t=0}^{T-1} \beta ^{t} u(x_{t}, x_{t+1}) + \beta ^{T} v(x_{T}) \right\} . \end{aligned}$$

(6.8)

Proof

Note from (2.15) and Remark 6.1 with $w = \overline{v}$ that $v_{n} \in V$ for all $n \in {{\mathbb {N}}}$. For any $x_{0} \in X$, we have

$$\begin{aligned} v_{1}(x_{0})&= \sup _{x_{1} \in \Gamma (x_{0})} \{u(x_{0}, x_{1}) + \beta v(x_{1})\} \end{aligned}$$

(6.9)

$$\begin{aligned}&= \sup _{x_{1} \in \Gamma (x_{0})} \sup _{\{x_{t}\}_{t=2}^{\infty } \in \Pi (x_{1})} \{u(x_{0}, x_{1}) + \beta v(x_{1})\} \end{aligned}$$

(6.10)

$$\begin{aligned}&= \sup _{\{x_{t}\}_{t=1}^{\infty } \in \Pi (x_{0})} \{u(x_{0}, x_{1}) + \beta v(x_{1})\}, \end{aligned}$$

(6.11)

where (6.10) holds because $\{u(x_{0}, x_{1}) + \beta v(x_{1})\}$ is independent of $\{x_{t}\}_{t=2}^{\infty }$,¹⁷ and (6.11) follows by combining the two suprema (see Kamihigashi 2008, Lemma 1). It follows that (6.8) holds for $T = 1$.

Now assume (6.8) for $T = n \in {{\mathbb {N}}}$. For any $x_{0} \in X$, we have

$$\begin{aligned} v_{n+1}(x_{0})&= \sup _{x_{1} \in \Gamma (x_{0})} \{u(x_{0}, x_{1}) + \beta v_{n}(x_{1})\} \end{aligned}$$

(6.12)

$$\begin{aligned}&= \sup _{x_{1} \in \Gamma (x_{0})} \Biggl \{u(x_{0}, x_{1}) \nonumber \\&\quad \quad + \beta \sup _{\{x_{i+1}\}_{i=1}^{\infty } \in \Pi (x_{1})} \Bigl \{ \sum _{i=0}^{n-1} \beta ^{i} u(x_{i+1}, x_{i+2}) + \beta ^{n} v(x_{n+1}) \Bigr \} \Biggr \} \end{aligned}$$

(6.13)

$$\begin{aligned}&= \sup _{x_{1} \in \Gamma (x_{0})} \sup _{\{x_{i+1}\}_{i=1}^{\infty } \in \Pi (x_{1})} \left\{ \sum _{t=0}^{n} \beta ^{t} u(x_{t}, x_{t+1}) + \beta ^{n+1} v(x_{n+1}) \right\} \end{aligned}$$

(6.14)

$$\begin{aligned}&= \sup _{\{x_{t}\}_{t=1}^{\infty } \in \Pi (x_{0})} \left\{ \sum _{t=0}^{n} \beta ^{t} u(x_{t}, x_{t+1}) + \beta ^{n+1} v(x_{n+1}) \right\} , \end{aligned}$$

(6.15)

where (6.13) uses (6.8) for $T=n$, (6.14) holds because $u(x_{0}, x_{1})$ is independent of $\{x_{i+1}\}_{i=1}^{\infty }$, and (6.15) follows by combining the two suprema (see Kamihigashi 2008, Lemma 1). It follows that (6.8) holds for $T = n+1$. By induction, (6.8) holds for all $T \in {{\mathbb {N}}}$. $\square$

Lemma 6.3

Let $\underline{v}, \overline{v} \in V$ satisfy (2.13)–(2.16). Then $\underline{v}^{*} \equiv \lim _{T \uparrow \infty } \underline{v}_{T} \ge v^{*}$.¹⁸

Proof

Note from (2.13)–(2.15), (2.11), and Remark 6.1 that $\{\underline{v}_{T}\}_{T=1}^{\infty }$ is an increasing sequence in $V$. Thus for any $x_{0} \in X$, we have

$$\begin{aligned} \underline{v}^{*}(x_{0})&= \sup _{T \in {{\mathbb {N}}}} \underline{v}_{T}(x_{0}) \end{aligned}$$

(6.16)

$$\begin{aligned}&= \sup _{T \in {{\mathbb {N}}}} \, \sup _{\{x_{t}\}_{t=1}^{\infty } \in \Pi (x_{0})} \left\{ \sum _{t=0}^{T -1} \beta ^{t} u(x_{t}, x_{t+1}) + \beta ^{T} \underline{v}(x_{T}) \right\} \end{aligned}$$

(6.17)

$$\begin{aligned}&= \sup _{\{x_{t}\}_{t=1}^{\infty } \in \Pi (x_{0})} \, \sup _{T \in {{\mathbb {N}}}} \left\{ \sum _{t=0}^{T-1} \beta ^{t} u(x_{t}, x_{t+1}) + \beta ^{T} \underline{v}(x_{T}) \right\} \end{aligned}$$

(6.18)

$$\begin{aligned}&\ge \sup _{\{x_{t}\}_{t=1}^{\infty } \in \Pi ^{0}(x_{0})} L_{T \uparrow \infty } \left\{ \sum _{t=0}^{T-1} \beta ^{t} u(x_{t}, x_{t+1}) + \beta ^{T} \underline{v}(x_{T}) \right\} \end{aligned}$$

(6.19)

$$\begin{aligned}&\ge \sup _{\{x_{t}\}_{t=1}^{\infty } \in \Pi ^{0}(x_{0})} \left\{ L_{T \uparrow \infty } \sum _{t=0}^{T-1} \beta ^{t} u(x_{t}, x_{t+1}) + {\underline{\lim }}_{T \uparrow \infty } \beta ^{T} \underline{v}(x_{T}) \right\} \end{aligned}$$

(6.20)

$$\begin{aligned}&\ge \sup _{\{x_{t}\}_{t=1}^{\infty } \in \Pi ^{0}(x_{0})} L_{T \uparrow \infty } \sum _{t=0}^{T-1} \beta ^{t} u(x_{t}, x_{t+1}) = v^{*}(x_{0}), \end{aligned}$$

(6.21)

where (6.17) uses Lemma 6.2, (6.18) follows by interchanging the two suprema (see Kamihigashi 2008, Lemma 1), (6.19) holds because $\Pi ^{0}(x_{0}) \subset \Pi (x_{0})$ (recall (2.8)) and $L_{T \uparrow \infty } a_{T} \le \sup _{T \in {{\mathbb {N}}}} a_{T}$ for any sequence $\{a_{T}\}$ in $[-\infty , \infty )$, (6.20) follows from the properties of ${\underline{\lim }}$ and ${\overline{\lim }}$,¹⁹ and the inequality in (6.21) uses (2.16). It follows that $\underline{v}^{*} \ge v^{*}$. $\square$

To complete the proof of Theorem 2.1, suppose that there exist $\underline{v}, \overline{v} \in V$ satisfying (2.13)–(2.17). The order interval $[\underline{v}, \overline{v}]$ is partially ordered by $\le$ (recall (2.10)). Given any $F \subset [\underline{v}, \overline{v}]$, we have $\sup F \in [\underline{v}, \overline{v}]$ because

$$\begin{aligned} {\forall }x \in X, \qquad (\sup F)(x) = \sup \{f(x) : f \in F\} \in [\underline{v}(x), \overline{v}(x)]. \end{aligned}$$

(6.22)

Since $B$ is a monotone operator, and since $B([\underline{v}, \overline{v}]) \subset [\underline{v}, \overline{v}]$ by (2.13)–(2.15) and (2.11), it follows that $B$ has a fixed point $v$ in $[\underline{v}, \overline{v}]$ by the Knaster–Tarski fixed point theorem (e.g., Aliprantis and Border 2006, p. 16). Since $\underline{v} \le v = B v$, we have $\underline{v}_{n} \le v$ for all $n \in {{\mathbb {N}}}$ by Remark 6.1; thus $\underline{v}^{*} \le v$.²⁰ Since $v \le v^{*}$ by Lemma 6.1 and $v^{*} \le \underline{v}^{*}$ by Lemma 6.3, it follows that $v \le v^{*} \le \underline{v}^{*} \le v$. Hence $v = \underline{v}^{*} = v^{*}$. Therefore, $v^{*}$ is a unique fixed point of $B$ in $[\underline{v}, \overline{v}]$; this establishes conclusions (a) and (b). Finally, conclusion (c) holds because $\underline{v}^{*} = v^{*}$.

1.2 Proof of Proposition 2.1

Let $\overline{v} \in V$ satisfy (2.17) and (2.18). Then by Lemma 6.1, any fixed point $v$ of $B$ with $v \le \overline{v}$ satisfies $v \le v^{*}$. Since $v^{*} \le \overline{v}$ and $v^{*}$ is a fixed point of $B$ by Lemma 2.1, it follows that $v^{*}$ is the largest fixed point of $B$ in $[-\infty , \overline{v}]$.

1.3 Proof of Therem 2.2

Let $\underline{v} \in V$ satisfy (2.14), (2.16), and (2.19). Since $B v^{*} = v^{*}$ by Lemma 2.1, (2.13)–(2.15) hold with $\overline{v} = v^{*}$. Hence, by Lemma 6.3, $\underline{v}^{*} \ge v^{*}$. Since $\underline{v} \le v^{*}$, we also have $\underline{v}^{*} \le v^{*}$. Thus $\underline{v}^{*} = v^{*}$. We have verified the second conclusion. If $B$ has a fixed point $v \in [\underline{v}, \infty ]$, then $v^{*} = \underline{v}^{*} \le v$; thus the first conclusion also holds.