10 Continuous-Time

Earlier chapters treated dynamics in discrete time. Now we switch to continuous time. We restrict ourselves to finite state spaces, where continuous-time processes are pure jump processes. This allows us to provide a rigorous and self-contained treatment, while laying foundations for a treatment of general state problems.

10.1Continuous-Time Markov Chains¶

In this section, we introduce continuous-time Markov models. In Section 10.2, we will use them as components of continuous-time Markov decision processes.

10.1.1Background¶

In Section 3.1.1 we learned that if $(X_t) = (X_0, X_1, \ldots)$ is $P$-Markov, then the distributions $(\psi_t)$ of the state process obey $\psi_{t+1} = \psi_t P$ for all $t$. This update rule is a linear difference equation in distribution space, which in turn suggests that, once we switch to continuous-time, distributions will evolve according to linear differential equations in distribution space.

This idea turns out to be correct. As such, we begin this chapter with some facts about linear differential equations.

10.1.1.1Scalar Exponentials¶

Solutions to linear differential equations involve exponential functions. The real-valued exponential function can be defined by the power series

The continuous-time system in Example 10.1.1 is closely related to the discrete time difference equation $u_{t+1} = \me^{r} u_t$. Indeed, if we start at $u_0$, then the $t$-th iterate is $\me^{r t} u_0$, so solutions agree at integer times. We can think of the continuous-time system as one that interpolates between points in time of a corresponding discrete time system.

The exponential $\me^\lambda$ of $\lambda = a + i b \in \CC$ can also be defined via (10.1). From the identity $\me^{ib} = \cos(b) + i \sin(b)$, we obtain

This equation will soon prove useful.

10.1.1.2The Exponential Distribution¶

A random variable $W$ is said to be exponentially distributed with rate $\theta$, and we write $W \eqdist \Exp(\theta)$, when the counter CDF $G$ satisfies

Continuous-time Markov chains have a close relationship with the exponential distribution, a fact that stems from its being the only distribution having the memoryless property

The memoryless property is special. For example, the probability that an individual human being lives 70 years from birth is not equal to the probability that he or she lives another 70 years conditional on having reached age 70. In fact, the exponential distribution is the only memoryless distribution supported on the nonnegative reals:

10.1.1.3Extension to Matrices¶

The real exponential formula (10.1) extends to the matrix exponential via

where $A$ is any square matrix. As we will see, the matrix exponential plays a key role in the solution of vector-valued linear differential equations.

In Lemma 10.1.2 and what follows, integration or differentiation of a vector- or matrix-valued function is carried out element by element. For example, to differentiate a matrix $B(t) = (b_{ij}(t))$ that depends on $t$, we form a new matrix by differentiating each element $b_{ij}(t)$ with respect to $t$. The integral $\int_a^b B(t) \diff t$ is the matrix of integrals $\int_a^b b_{ij}(t) \diff t$.

The proof of part (ii) of Lemma 10.1.2 uses the definition of the exponential and the binomial formula. See, for example, Hirsh & Smale (1974). Part (iii) follows directly from part (ii). Part (iv) follows easily from part (i) when $A$ is diagonalizable (and can be proved more generally via the Jordan canonical form).

As for (vii), we are drawing an analogy with the fundamental theorem of calculus for scalar-valued functions, which states that $f(t) - f(s) = \int_s^t f'(\tau) \diff \tau$ for all $s \leq t$, where $f'$ is the derivative of $f$.

10.1.2Continuous-Time Flows¶

Next, we study solutions of multivariate differential equations, with a focus on linear systems. These results lay foundations for our study of continuous-time Markov dynamics in Section 10.1.3.

10.1.2.1Continuous-Time Dynamical Systems¶

Recall from Section 2.1.1 that a discrete dynamical system is a pair $(U, S)$, where $U$ is a set and $S$ is a self-map on $U$. Trajectories are sequences $(S^t u)_{t \geq 0} = (u, Su, S^2 u, \ldots)$, where $u \in U$ is the initial condition. These ideas can be extended to continuous-time by considering a pair $(U, (S_t)_{t \geq 0})$ where $U$ is any set and $S_t$ is a self-map on $U$ for each $t \in \RR_+$. The interpretation is that if $u \in U$ is the current state of the system, then $S_t u$ will be the state after $t$ units of time.

In general, to understand $(U, (S_t)_{t \geq 0})$ as a continuous-time dynamical system, we require that (a) $S_0$ is the identity map, so that the state after zero units of time is just the initial condition, and (b) if we start at $u$, move forward to $u_s \coloneq S_s u$, and then move again to $S_t u_s$ after another $t$ units of time, the outcome should be the same as moving from $u$ to $S_{s \,+\, t} \, u$ directly. That is,

This is the semigroup property.

One way that continuous-time dynamical systems arise is via initial value problems. An initial value problem (IVP) in $\RR^n$ consists of a differential equation $\dot u_t = f(u_t)$ paired with an initial condition $u_0 \in \RR^n$, where $u_t \in \RR^n$ and $f \colon \RR^n \to \RR^n$. Under suitable conditions on $f$, the solution $u_t \coloneq F(t, u_0)$ is uniquely defined for all $t \geq 0$, and, moreover,

(see, e.g., Hirsh & Smale (1974), Section 8.7). Hence $(S_t)_{t \geq 0}$ defined by $S_t u = F(t, u)$ satisfies the semigroup property and $(\RR^n, (S_t)_{t \geq 0})$ is a continuous-time dynamical system. The function $f$ is called the vector field of $(\RR^n, (S_t)_{t \geq 0})$.

10.1.2.2Linear Initial Value Problems¶

Given our interest in continuous-time Markov chains and their connection to linear systems (see the comments at the start of Section 10.1.1), we focus primarily on linear differential equations. The next result discusses linear IVPs, illustrating the key role of the matrix exponential. In the statement, $A$ is $n \times n$ and both $\dot u_t$ and $u_t$ are column vectors in $\RR^n$.

(Here $\dot u_t \coloneq \diff u_t / \diff t$ is defined by differentiating the vector $u_t$ element-by-element, as discussed after Lemma 10.1.2.)

Proposition 10.1.3 motivates us to study flows of the form

where $A$ is $n \times n$, $u_0$ is a vector in $\RR^n$ indicating the initial condition, and $u_t$ is the “state” of the system at time $t$. Figure Figure 10.1 shows an example when

10.1.2.3Stability in the Diagonalizable Case¶

For an exponential flow such as (10.24), a key question is whether or not $u_t \to 0$ as $t \to \infty$. (This will matter when we try to evaluate lifetime rewards over an infinite horizon in continuous time.) Rather than analyze these issues at every possible $u_0$, we directly consider the matrix-valued flow $t \mapsto \me^{ t A}$ and study whether $\me^{tA} \to 0$.

The case where $A$ is diagonalizable provides a good starting point. Suppose $A = P^{-1} D P$ with $D = \diag_j (\lambda_j)$ containing the eigenvalues of $A$. Then, by Lemma 10.1.2, for any $t \geq 0$, we have

Exercise 10.8 and equation (10.26) tell us that the long run dynamics of $\me^{tA}$ are determined by the scalar flows $t \mapsto \me^{t \lambda_j}$. How does $\me^{t \lambda}$ evolve over time when $\lambda \in \CC$?

To answer this question we write $\lambda = a + ib$ and apply (10.4) to obtain

This equation tells us that

where $\real \lambda$ is the real part of $\lambda$ (i.e., if $\lambda = a + ib$, then $\real \lambda = a$).

From this analysis, we conclude that, when $A$ is diagonalizable, we have $\me^{tA} \to 0$ if and only if $\real \lambda_j < 0$ for all $\lambda_j \in \sigma(A)$, where $\sigma(A)$ denotes the set of all eigenvalues (the spectrum) of $A$. Another way to put this is that $\me^{tA} \to 0$ if and only if $s(A) < 0$, where

is the spectral bound of $A$.

As the preceding analysis suggests, the spectral bound plays a key role in the asymptotics of exponential flows, just as a spectral radius governs asymptotics of trajectories of linear maps (see, e.g., Exercise 1.14). Section Section 10.1.2.4 expands on this analysis, while dropping the assumption that $A$ is diagonalizable.

10.1.2.4The General Case¶

Let $A$ be any square matrix. In the following statement about a spectral bound, $\| \cdot \|$ is the operator norm defined in Section 1.2.1.4.

(The second equality in (10.30) also holds when the limit is taken over $t \in \RR_+$. See, for example, Engel & Nagel (2006).)

The next theorem is a key stability result for exponential flows. Among other things, it extends to arbitrary $A$ the finding that $s(A) < 0$ is necessary and sufficient for stability.

A full proof of Theorem 10.1.5 in a general setting can be found in §V.II of Engel & Nagel (2006).

Theorem 10.1.5 tells us that the flow $t \mapsto \me^{tA} u_0$ converges to the origin at an exponential rate if and only if $s(A)<0$. The equivalence of (i) and (ii) was proved for the diagonalizable case in Section 10.1.2.3. It can be viewed as the continuous-time analog of $\|B^k\| \to 0$ if and only if $\rho(B) < 1$ (see Exercise 1.14).

10.1.2.5Semigroup Terminology¶

Advanced treatments of continuous-time systems often begin with semigroups. Let’s briefly describe these and connect them to things we have studied earlier. (If you prefer to skip this section on first reading, you can move to the next one after noting that, given an $n \times n$ matrix $A$, the family $(S_t)_{t \geq 0} = (\me^{t A})_{t \geq 0}$ is called an exponential semigroup and that $A$ is called the infinitesimal generator of the semigroup.)

Let $\Xsf$ be a finite set and let $(S_t)_{t \geq 0}$ be a subset of $\lopx$ indexed by $t \in \RR_{+}$. The family $(S_t)_{t \geq 0}$ is called a strongly continuous semigroup or $C_0$-semigroup on $\RR^\Xsf$ if

1. $S_0 = I$, where $I$ is the identity,

2. $S_{t + \, t'} = S_t \circ S_{t'}$, and

3. $t \mapsto S_t u$ is a continuous map from $\RR_+$ to $\RR^\Xsf$ for every $u \in \RR^\Xsf$.

In essence, a $C_0$-semigroup on $\RR^\Xsf$ is a continuous-time dynamical system $(\RR^\Xsf, (S_t)_{\, t \geq 0})$ where each $S_t$ maps an initial state into a time $t$ state.

The semigroup perspective is important because it extends naturally to settings where $\Xsf$ is not finite, in which case we replace the finite-dimensional set $\RR^\Xsf$ with some (typically infinite-dimensional) class of functions $\gG \subset \RR^\Xsf$, and each $S_t$ becomes a linear operator mapping $\gG$ into itself. At this level of generality, $S_t u$ can be the solution to a partial differential equation, or a stochastic differential equation (see, e.g., Engel & Nagel (2006) or Applebaum (2019)). Operator semigroup theory offers an elegant and powerful framework for handling such systems.

For semigroups in general settings we often have no analytical expressions for $S_t$. This situation is like the one we encountered in the continuous-time system in Section 10.1.2.1, where $\dot u_t = f(u_t)$ and $f$ is potentially nonlinear. When no analytical solution $u_t$ exists, analyzing the dynamics requires us to try to infer its properties from the vector field $f$, so that $f$ becomes the primary focus of analysis.

A natural question, then, is, given a semigroup $(S_t)_{\, t \geq 0}$ on $\lopx$, does there always exist a “vector field” type object that “generates” $(S_t)_{\, t \geq 0}$? When $\Xsf$ is finite, the answer is affirmative. This object, to be denoted by $A$, is called the infinitesimal generator of the semigroup and is defined by

At $u \in U$, the vector $A u$ indicates the instantaneous change in the state.

More precisely, when $\Xsf$ is finite, we have:

Semigroups of the form described in Proposition 10.1.6 are called exponential semigroups (or “uniformly continuous” semigroups).

A full proof of Proposition 10.1.6 can be found in the discussion of Theorem 2.12 of Engel & Nagel (2006). The results are not surprising, since the main claim is that, in finite dimensions, solutions to linear differential equations have exponential form. The fact that $A$ is the infinitesimal generator of the semigroup $(S_t)_{\, t \geq 0} = (\me^{tA})_{\, t \geq 0}$ follows from Lemma 10.1.2, which gives

The preceding discussion places our analysis in a wider context. To practice our new terminology, we can restate (i) $\iff$ (ii) from Theorem 10.1.5 by saying that the exponential semigroup $(S_t)_{\, t \geq 0} = (\me^{tA})_{\, t \geq 0}$ converges to zero if and only if the spectral bound of its infinitesimal generator is negative.

10.1.3Markov Semigroups¶

Having studied multivariate linear dynamics, we are now ready to concentrate on the Markov case, where dynamics evolve in distribution space. For the most part we now switch to operator-theoretic notation, where $\Xsf$ is a finite set with $n$ elements, and an $n \times n$ matrix is identified with a linear operator on $\lopx$. As emphasized in Section 2.3.3.1, this is merely a change in terminology, and all preceding results for matrices extend directly to linear operators.

10.1.3.1Intensity Matrices¶

If $(X_t)_{\, t \geq 0}$ is $P$-Markov on $\Xsf$ for some $P \in \mopx$, then the marginal distributions of $(X_t)_{t \geq 0}$ evolve according to the linear difference system $\psi_{t+1} = \psi_t P$ (see Section 3.1.1). We now seek a continuous-time analog in the form of a linear differential equation.

To this end we call $Q \in \lopx$ an intensity operator or intensity matrix^[1] when

Let

Consider the IVP

which we can also write as

when $\psi_t$ and $\dot \psi_t$ are understood to be row vectors. We say that $\dD(\Xsf)$ is invariant for the IVP (10.40) if the solution $(\psi_t)_{t \geq 0}$ remains in $\dD(\Xsf)$ for all $t \geq 0$.

In view of Proposition 10.1.3, we can rephrase this by stating that $\dD(\Xsf)$ is invariant for (10.40) whenever

Our key result for this section shows the central role of intensity matrices:

Proposition 10.1.7 tells us that the set $\iopx$ coincides with the set of continuous-time (and time-homogeneous) Markov models on $\Xsf$. Any specification outside this class fails to generate flows in distribution space. The proof is completed in several steps.

For Exercise 10.13--Exercise 10.15, $Q \in \iopx$ and $P_t \coloneq \me^{tQ}$.

For the proof of Proposition 10.1.7, we have now shown that (i) implies (ii). Evidently (ii) implies (iii), because if $\psi_0 \in \dD$ and $\psi_t = \psi_0 P_t$ where $P_t$ is stochastic, then $\psi_t \in \dD(\Xsf)$. Hence it remains only to show that (iii) implies (i).

Returning to Proposition 10.1.7, the last two exercises confirm that (iii) implies (i). The proof is now complete.

10.1.3.2Interpretation¶

Section Section 10.1.3.1 covered the mathematical relationship between intensity matrices and Markov operators. Let’s now discuss the connection more informally, in order to build intuition.

To this end, let $(X_t)_{t \geq 0}$ be $P_h$-Markov in discrete time. Here $h > 0$ is the length of the time step. We write the corresponding distribution sequence $\psi_{t+h} = \psi_t P_h$ in terms of change per unit of time, as in

Continuous-time dynamics are obtained by taking the limit as $h \, \downarrow \, 0$. If we define

and assume that limits exist, then (10.47) becomes (10.40).

What properties does $Q$ have? Inspecting (10.48) implies

when $h$ is small and positive.

Equation (10.50) tells us that $Q(x, x')$ represents the instantaneous rate of flow out of state $x$ and into state $x'$. The on-diagonal value $P_h(x,x)$ just balances the off-diagonal probabilities.

10.1.3.3Markov Semigroups¶

Fix $Q \in \iopx$. In the terminology of Section 10.1.2.5, the family of operators $(P_t)_{t \geq 0} = (\me^{tQ})_{t \geq 0} \subset \mopx$ that solves $\dot \psi_t = \psi_t Q$ (see (10.41)) is an exponential semigroup. Since each $P_t$ is in $\mopx$, it is also called the Markov semigroup generated by $Q$. It satisfies the semigroup property $P_{s \, + \, t} = P_s \, P_t$ for all $s, t \geq 0$, which can be written more explicitly as

In the present setting, (10.52) is called the (continuous-time) Chapman--Kolmogorov equation. It states that the probability of moving from $x$ to $x'$ over $s+t$ units of time equals the probability of moving from $x$ to $z$ over $s$ units of time, and then $z$ to $x'$ over $t$ units of time, summed over all $z$.

Again following the terminology in Section 10.1.2.5, the intensity matrix $Q$ that defines $(P_t)_{t \geq 0} = (\me^{tQ})_{t \geq 0}$ is also called the infinitesimal generator of $(P_t)_{t \geq 0}$.

From Lemma 10.1.2, the derivative of $\me^{tQ}$ is $Q\me^{tQ} = \me^{tQ}Q$. We can write this as

• $\dot P_t = QP_t$, which is called the Kolmogorov backward equation, and

• $\dot P_t = P_t Q$, which is called the Kolmogorov forward equation.

We can work in the other direction as well: If we can establish that a function $t \mapsto P_t$ from $\RR_+$ to $\lopx$ satisfies either one of these equations, then $(P_t)_{t \geq 0}$ is a Markov semigroup with infinitesimal generator $Q$. The next proposition gives details.

Proposition 10.1.8 is a version of our result for linear IVPs in Proposition 10.1.3, except that the IVP is now defined in operator space, rather than vector space.

10.1.4Continuous-Time Markov Chains¶

We have discussed the connection between intensity matrices, Markov semigroups, and distribution flows. Let’s now connect these objects to continuous-time Markov chains. In this section, we will (a) provide a formal definition of a continuous-time Markov chain associated with a given initial condition $\psi$ and intensity matrix $Q$, and (b) show how to construct such a chain algorithmically. We’ll accomplish (b) in two steps: first showing how to construct a jump chain from certain primitives (Section 10.1.4.2--Section 10.1.4.3) and then showing how to construct those primitives from a given initial condition $\psi$ and intensity matrix $Q$ (Section 10.1.4.4).

10.1.4.1Definition¶

Let $C(\RR_+, \Xsf)$ be the set of right-continuous functions from $\RR_+$ to $\Xsf$ and let $(P_t)_{t \geq 0}$ be a Markov semigroup generated by some $Q \in \iopx$. A continuous-time Markov chain generated by $(P_t)_{t \geq 0}$ is a random function $(X_t)_{t \geq 0}$ that takes values in $C(\RR_+, \Xsf)$ and satisfies

where $\fF_s \coloneq (X_\tau)_{0 \leq \tau \leq s}$ is the history of the process up to time $s$. To update from time $s$ to time $t$ given this history, we simply take the last value $X_s$ and update using $P_t$. Conditioning on $X_s = x$, we get

Mirroring terminology for discrete chains from Section 3.1.1.1, we will call a continuous-time Markov chain $(X_t)_{t \geq 0}$ $Q$-Markov when (10.53) holds and $Q$ is the infinitesimal generator of $(P_t)_{t \geq 0}$.

In what follows, $\PP_x$ and $\EE_x$ denote probabilities and expectations conditional on $X_0 = x$. Given $h \in \RR^\Xsf$, we have

This expression mirrors the discrete time case discussed in Section 3.2.1.1.

10.1.4.2A Jump Chain Construction¶

In Section 10.1.4.1 we defined a continuous-time Markov chain. In this section, we describe a standard method for constructing one by using three components:

1. an initial condition $\psi \in \dD(\Xsf)$,

2. a jump matrix $\Pi \in \mopx$, and

3. a rate function $\lambda$ mapping $\Xsf$ to $(0, \infty)$.

The process $(X_t)$ starts at state $x$, which is drawn from $\psi$, waits there for an exponential time $W$ with rate $\lambda(x)$, and then updates to a new state $x'$ drawn from $\Pi(x, \cdot)$. We take $x'$ as the new state for the process and repeat.

These ideas are restated in Algorithm 10.1. In the algorithm, $(W_k)$ and $(Y_k)$ are drawn independently. The process $(W_k)$ is called the sequence of holding times or wait times, the sums $J_k = \sum_{i=1}^k W_i$ are called the jump times and $(Y_k)$ is called the embedded jump chain. The jumps and the process $(X_t)_{t \geq 0}$ are illustrated in Figure Figure 10.2.

Let $I \in \lopx$ be the identity matrix, so $I(x,x') = \1\{x = x'\}$, and define $Q \in \lopx$ via

It is easy to verify that $Q$ is an intensity matrix. In fact, $Q$ is the intensity matrix for the Markov semigroup associated with the process generated by Algorithm 10.1. For $x \not= x'$, it tells us that probability flows from $x$ to $x'$ at rate $\lambda(x) \Pi(x, x')$, which is the rate of leaving $x$ times the rate of moving from $x$ to $x'$. The next result formalizes these ideas.

To prove Proposition 10.1.9 we take $(X_t)_{t \geq 0}$ to be as in the statement of the proposition and define $(P_t)_{t \geq 0}$ by $P_t(x, x') = \PP_x \{X_t = x'\}$ for all $x,x' \in \Xsf$. The proof uses the following steps:

1. Obtain an integral equation that $(P_t)_{t \geq 0}$ must satisfy.

2. Differentiate to obtain the Kolmogorov backward equation $\dot P_t = QP_t$.

3. Solve this differential equation to obtain $P_t = \me^{t Q}$ for all $t$.

Here is the first step. In the statement, $\Pi P_{t-\tau}$ is the matrix product of $\Pi$ and $P_{t-\tau}$, while the equation in (10.57) is sometimes called the integrated Kolmogorov backward equation.

Differentiating the integrated Kolmogorov backward equation produces the Kolmogorov backward equation:

10.1.4.3Application: Inventory Dynamics¶

Let $X_t$ be a firm’s inventory at time $t$. When current stock is $x > 0$, customers arrive at rate $\lambda(x)$, so the wait time for the next customer is an independent draw from the $\Exp (\lambda(x))$ distribution; $\lambda$ maps $\Xsf$ to $(0, \infty)$.

The $k$-th customer demands $U_k$ units, where each $U_k$ is an independent draw from a fixed distribution $\phi$ on $\NN$. Purchases are constrained by inventory, however, so inventory falls by $U_k \wedge X_t$. When inventory hits zero the firm orders $b$ units of new stock. The wait time for new stock is also exponential, being an independent draw from $\Exp (\lambda(0))$.

Let $Y$ represent the inventory size after the next jump (induced by either a customer purchase or ordering new stock), given current stock $x$. If $x > 0$, then $Y$ is a draw from the distribution of $x - U \wedge x$ where $U \sim \phi$. If $x=0$, then $Y \equiv b$. Hence $Y$ is a draw from $\Pi(x, \cdot)$, where $\Pi(0, y) = \1\{y=b\}$ and, for $0 < x \leq b$,

We can simulate the inventory process $(X_t)_{t \geq 0}$ via the jump chain algorithm. In this case, the wait time sequence $(W_k)$ is the wait time for customers (and for inventory when $X_t=0$) and the jump sequence $(Y_k)$ is the level of inventory immediately after each jump. By Proposition 10.1.9, the inventory process is $Q$-Markov with $Q$ given by $Q(x, x') = \lambda(x)(\Pi(x, x') - I(x,x'))$.

Figure Figure 10.3 shows a simulation when orders are geometric, so that

In the simulation we set $\alpha=0.7$, $b=10$ and $\lambda(x) \equiv 0.5$. The figure plots $X_t$ for $t \in [0, 50]$. Since each wait time $W_i$ is a draw from $\Exp(0.5)$ the mean wait time is 2.0. The function that produces the map $t \mapsto X_t$ is shown in Listing 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using Random, Distributions

"""
Generate a path for inventory starting at b, up to time T.

Return the path as a function X(t) constructed from (J_k) and (Y_k).
"""
function sim_path(; T=10, seed=123, λ=0.5, α=0.7, b=10)

    J, Y = 0.0, b
    J_vals, Y_vals = [J], [Y]
    Random.seed!(seed)
    φ = Exponential(1/λ)     # Wait times are exponential
    G = Geometric(α)         # Orders are geometric

    while true
        W = rand(φ)  
        J += W
        push!(J_vals, J)
        if Y == 0
            Y = b
        else
            U = rand(G) + 1   # Geometric on 1, 2,...
            Y = Y - min(Y, U)
        end
        push!(Y_vals, Y)
        if J > T
            break
        end
    end
    
    function X(t)
        k = searchsortedlast(J_vals, t)
        return Y_vals[k+1]
    end

    return X
end

10.1.4.4From Intensity Matrices to Jump Chains¶

If $Q \in \lopx$ is a given intensity matrix, how should we produce a continuous-time $Q$-Markov chain? If we can construct a jump chain that is $Q$-Markov, then not only do we obtain existence of a $Q$-Markov chain but we also provide a way to simulate one (via Algorithm 10.1).

To construct such a jump chain we first fix an intensity matrix $Q \in \lopx$ and, to simply matters, assume that all rows of $Q$ are nonzero. This means that the process has no absorbing states (since nonzero rows are equivalent to $Q(x,x) < 0$ for all $x$, which in turn states that there is a nonzero outflow from each state).

Then we set

It is straightforward to confirm that $\Pi \in \mopx$ and that $Q$ satisfies (10.56). Hence, by Proposition 10.1.9, the process $(X_t)_{t \geq 0}$ generated by Algorithm 10.1 is $Q$-Markov.

10.2Continuous-Time Markov Decision Processes¶

We are ready to turn to dynamic programming in continuous-time. As for the discrete time case, continuous-time dynamic programs aim to maximize a measure of lifetime value. In Section 10.2.1 we study lifetime valuations. In Section 10.2.2 we learn how to maximize them.

10.2.1Valuation¶

In this section, we consider lifetime valuations associated with continuous reward flows, starting from a general semigroup perspective and then progressing to specific cases (such as expected lifetime value under constant discounting). Throughout, $\Xsf$ is a finite set.

10.2.1.1A Semigroup Perspective¶

For the discrete time problems with state-dependent discounting that we studied in Chapter 6, lifetime valuations take the form $v = \sum_{t \geq 0} K^t h$ for some $h \in \RR^\Xsf$ and a positive linear operator $K$ on $\RR^\Xsf$. (See Theorem 6.1.1 and (6.31).) For a continuous-time version we fix $h \in \RR^\Xsf$, take $(K_t)_{t \geq 0}$ to be a positive exponential semigroup in $\lopx$, where positive means $K_t \geq 0$ for all $t$, and set

Let $A \in \lopx$ be the infinitesimal generator of $(K_t)_{\, t \geq 0}$. The next result provides a condition for finiteness of $v$ and several characterizations.

A way to understand (10.69) is to view the valuation $v$ as a price that reflects prospective benefits from holding an asset. The asset yields a flow of benefits, where $h(x)$ is the instantaneous reward in state $x$. Rewards $t$ periods in the future are discounted by the pricing operator $K_t$. Thus, $(K_t h)(x)$ is the anticipated payoff $t$ periods ahead, discounted for the wait time and possibly also for risk as in (6.54). The value $v(x)$ is then lifetime value, which equals the current price.

In this asset valuation setting, (10.69) is a natural consistency condition. It says that the price of purchasing the asset today is equal to the payouts obtained from holding the asset from now until time $t$ and then selling it for current discounted value $K_t v$. (This is the continuous-time analog of (6.57).)

The preceding discussion matches the semigroup perspective on asset pricing introduced in Garman (1985) and Duffie & Garman (1986). In addition to shedding light on (10.69), it also leads to the assertion that $v = - A^{-1} h$ in (ii), which is obtained by differentiating (10.69). Details are in the proof:

10.2.1.2Valuations as Expectations¶

In applications, the expression $v = \int_0^\infty K_t \, h \diff t$ from (10.68) typically arises as a discounted expectation over a flow of rewards. When analyzing $v$ we wish to deploy Proposition 10.2.1, so we need to check that any expectation we propose results in $(K_t)$ being a semigroup. The next proposition provides one result along these lines.

In the proof of Proposition 10.2.2, we will use the fact that $(X_t)_{t \geq 0}$ satisfies the Markov property. In particular, if $H$ is a real-valued function on the path space $C(\RR_+, \Xsf)$, then

For a proof of (10.76), see, for example, Chapter 2 of Liggett (2010).

10.2.1.3Constant Discounting¶

Many studies of continuous-time dynamic programming with discounting use a constant discount rate. In this setting, the lifetime value in (10.68) becomes

for some $\delta \in \RR$ and $h \in \RR^\Xsf$. Here $(X_t)_{t \geq 0}$ is a continuous-time Markov chain on finite state $\Xsf$ generated by Markov semigroup $(P_t)_{t \geq 0}$ with intensity operator $Q$. The idea is that $h(X_t)$ is an instantaneous reward at each time $t$, while $\delta$ is a fixed discount rate.

Equation (10.82) is the continuous-time version of (3.33).

10.2.2Constructing a Decision Process¶

In this section, we define continuous-time Markov decision processes, discuss optimality theory, and provide algorithms and applications.

10.2.2.1Definition¶

Given two finite sets $\Asf$ and $\Xsf$, called the state and action spaces respectively, we define a continuous-time Markov decision process (or continuous-time MDP) to be a tuple $\cC = (\Gamma, \delta, r, Q)$ consisting of

1. a nonempty correspondence $\Gamma$ from $\Xsf$ to $\Asf$, referred to as the feasible correspondence, which in turn defines the feasible state-action pairs

2. a constant $\delta > 0$, referred to as the discount rate,

3. a function $r$ from $\Gsf$ to $\RR$, referred to as the reward function, and

4. an intensity kernel $Q$ from $\Gsf$ to $\Xsf$; that is, a map $Q$ from $\Gsf \times \Xsf$ to $\RR$ satisfying

and $Q(x, a, x') \geq 0$ whenever $x \not= x'$.

Informally, at state $x$ with action $a$ over the short interval from $t$ to $t+h$, the controller receives instantaneous reward $r(x,a)h$ and the state transitions to state $x'$ with probability $Q(x, a, x') h + o(h)$.

Paralleling our discussion of the discrete time case in Chapter 5, the set of feasible policies is

10.2.2.2Lifetime Values¶

Choosing policy $\sigma$ from $\Sigma$ means that we respond to state $X_t$ with action $A_t \coloneq \sigma(X_t)$ at every $t \geq 0$. The state then evolves according to the intensity operator

Letting

the lifetime value of following $\sigma$ starting from state $x$ is

where $(X_t)_{t \geq 0}$ is $Q_\sigma$-Markov with initial condition $x$. We call $v_\sigma$ the $\sigma$-value function.

Since $\delta > 0$, we can apply Proposition 10.2.3 to obtain

Representation (10.94) provides a straightforward method for computing $v_\sigma$.

10.2.2.3Greedy Policies¶

A policy $\sigma \in \Sigma$ is called $v$-greedy for $\cC$ if

Like the discrete time case, a $v$-greedy policy chooses actions optimally to trade off high current rewards versus high rate of flow into future states with high values. Unlike the discrete time case, the discount factor does not appear in (10.95) because the trade-off is instantaneous.

10.2.2.4Policy Iteration¶

We introduce a continuous-time policy iteration algorithm that parallels discrete time HPI for Markov decision processes, as described in Section 5.1.4.2.

The continuous-time HPI routine is given in Algorithm 10.2, with the intuition being similar to that for the discrete time MDP version given. We provide convergence results in Section 10.2.3.

10.2.2.5Policy Operators¶

For each $\sigma \in \Sigma$, let $T_\sigma$ be the operator defined at $v \in \RR^\Xsf$ by

As shown in Proposition 10.2.3, each $T_\sigma$ is order stable on $\RR^\Xsf$, with unique fixed point $v_\sigma$. Hence $\aA \coloneq (\RR^\Xsf, \{T_\sigma\})$ is an order stable ADP.