Optimal Timing to Initiate Medical Treatment for a Disease Evolving as a Semi-Markov Process

Abstract

In this paper, we consider the problem of the optimal timing to initiate a medical treatment. In the absence of treatment, we model the disease evolution as a semi-Markov process. The optimal time to initiate the treatment is a stopping time, which maximizes the total expected reward for the patient. We propose a stochastic dynamic programming formulation to find this stopping time. Under some plausible conditions, we show that the maximum total expected reward at the start of a health state will be smaller when the patient is in a more severe state. We then prove that the optimal policy for initializing the treatment is determined by a time threshold for each given health state. That is, in each health state, the treatment should be planned to start, when the patient’s duration time in the health state reaches (or exceeds, in the case of a late observation of the patient’s health status) a certain threshold level. We also present numerical examples to illustrate our model and to provide managerial insights.

Appendices

Appendix A: Proof of Proposition 2.1

Proof

According to Lemma 2.1 in Boshuizen and Gouweleeuw [11], for any $k\ge 1$ there exists a random variable $\tau _{k}\ge 0$ such that ${\mathcal {T}}\wedge T_{k}=\left( T_{k-1}+\tau _{k}\right) \wedge T_{k}$, and $\tau _{k}$ is ${\mathcal {F}}(T_{k})$-measurable with ${\mathcal {F}}(s)$ standing for the $\sigma$-algebra generated by $\left\{ Z(t),t\le s\right\}$. (That is, $\tau _{k}$ reduces to a deterministic number when $T_{k}$ is known.) It is equivalent to use the objective function $P({\mathcal {T}})-P(T_{n}+t)$ in place of $P({\mathcal {T}})$.

Let $\tilde{V}(i,t)=\max _{{\mathcal {T}}\ge T_{n}+t}\left\{ P({\mathcal {T}} )-P(T_{n}+t)\mid X_{n}=i,S_{n}>t\right\} \text {.}$

Then, $\tilde{V}(i,t)=V(i,t)-E\left\{ P(T_{n}+t)\mid X_{n}=i,S_{n}>t\right\} =V(i,t)-R(i)$. We have

$$\begin{aligned}&E\left[ P({\mathcal {T}})-P(T_{n}+t)\mid X_{n}=i,S_{n}>t\right] \\&\quad = E\left\{ \left[ P({\mathcal {T}}\wedge T_{n+1})-P(T_{n}+t)\right] I_{\left\{ {\mathcal {T}}<T_{n+1}\right\} }\mid X_{n}=i,S_{n}>t\right\} \\&\qquad +E\left\{ \left[ P({\mathcal {T}}\vee T_{n+1})-P(T_{n+1})\right] I_{\left\{ {\mathcal {T}}\ge T_{n+1}\right\} }\mid X_{n}=i,S_{n}>t\right\} \\&\qquad +E\left\{ \left[ P(T_{n+1})-P(T_{n}+t)\right] I_{\left\{ {\mathcal {T}}\ge T_{n+1}\right\} }\mid X_{n}=i,S_{n}>t\right\} \\&\quad = E\left\{ \left[ P({\mathcal {T}}\wedge T_{n+1})-P(T_{n}+t)\right] \mid X_{n}=i,S_{n}>t\right\} \\&\qquad +E\left\{ \left[ P({\mathcal {T}}\vee T_{n+1})-P(T_{n+1})\right] I_{\left\{ {\mathcal {T}}\ge T_{n+1}\right\} }\mid X_{n}=i,S_{n}>t\right\} \\&\quad = E\left\{ \left[ P\left( \left( T_{n}+\tau _{n+1}\right) \wedge T_{n+1}\right) -P(T_{n}+t)\right] \mid X_{n}=i,S_{n}>t\right\} \\&\qquad +E\left\{ \left[ P({\mathcal {T}}\vee T_{n+1})-P(T_{n+1})\right] I_{\left\{ S_{n}\le \tau _{n+1}\right\} }\mid X_{n}=i,S_{n}>t\right\} \\&\quad = E\left\{ \left[ P\left( \left( T_{n}+\tau _{n+1}\right) \wedge T_{n+1}\right) -P(T_{n}+t)\right] \mid X_{n}=i,S_{n}>t\right\} \\&\qquad +E\left\{ E\left[ P({\mathcal {T}}\vee T_{n+1})-P(T_{n+1})\mid X_{n+1},S_{n+1}>0\right] I_{\left\{ S_{n}\le \tau _{n+1}\right\} }\mid X_{n}=i,S_{n}>t\right\} . \end{aligned}$$

In order to maximize $E\left[ P({\mathcal {T}})\mid X_{n}=i,S_{n}>t\right]$ with respect to ${\mathcal {T}}$, we can maximize with respect to $\tau _{n+1}$ and ${\mathcal {T}}\vee T_{n+1}$ separately. Note that an arbitrary stopping time $\tilde{\mathcal {T}}\ge T_{n+1}$ can be written into the form ${\mathcal {T}}\vee T_{n+1}$.

$$\begin{aligned} \tilde{V}(i,t)&=E\left\{ \left[ P\left( \left( T_{n}+\tau _{n+1}\right) \wedge T_{n+1}\right) -P(T_{n}+t)\right] \mid X_{n}=i,S_{n}>t\right\} \nonumber \\&\quad +E\left\{ \tilde{V}(X_{n+1},0)I_{\left\{ S_{n}\le \tau _{n+1}\right\} }\mid X_{n}=i,S_{n}>t\right\} . \end{aligned}$$

(6)

The term $P\left( \left( T_{n}+\tau _{n+1}\right) \wedge T_{n+1}\right) -P(T_{n}+t)$ is the reward difference between initializing treatment at difference times. If $S_{n}>\tau _{n}$, then the health state equals i when treatment starts for both starting time epochs. Otherwise, the health state is $X_{n}$ at $\left( T_{n-1}+\tau _{n}\right) \wedge T_{n}=T_{n}$ and is i at $T_{n-1}+t$. Therefore, we have

$$\begin{aligned}&E\left\{ P\left( \left( T_{n-1}+\tau _{n}\right) \wedge T_{n}\right) -P(T_{n-1}+t)\mid X_{n-1}=i,S_{n}>t\right\} \\&=E\left\{ \left[ \left( T_{n-1}+\tau _{n}\right) \wedge T_{n}-(T_{n-1}+t) \right] r(i)\mid X_{n-1}=i,S_{n}>t\right\} \\&\quad +E\left\{ \left[ R(X_{n})-R(i)\right] I_{\left\{ S_{n}\le \tau _{n}\right\} }\mid X_{n-1}=i,S_{n}>t\right\} \\&=r(i)\left[ E\left( \tau _{n}\wedge S_{n}\mid X_{n-1}=i,S_{n}>t\right) -t \right] \\&\quad +E\left\{ \left[ R(X_{n})-R(i)\right] I_{\left\{ S_{n}\le \tau _{n}\right\} }\mid X_{n-1}=i,S_{n}>t\right\} . \end{aligned}$$

Because $\tilde{V}(j,t)=V(j,t)-R(j)$ for all $j\in {\mathcal {H}}$, we can write (6) in terms of V, as in Eqs. (4)–(5). $\square$

Appendix B: Proof of Lemma 3.1

Proof

To prove the lemma, it is equivalent to show that $\Pr \left( X_{n+1}(i,^{\le }s)\ge j\right)$ increases in s for all $j\in {\mathcal {H}}$.

It is easy to verify that

$$\begin{aligned} \Pr \left( X_{n+1}(i,^{\le }s)\ge j\right)&=\sum _{z=1}^{s}\frac{\Pr \left( S_{n}(i)=z\right) }{\Pr \left( S_{n}(i)\le s\right) }\cdot \Pr \left( X_{n+1}(i,z)\ge j\right) \\&=\sum _{z=1}^{s-1}\frac{\Pr \left( S_{n}(i)=z\right) }{\Pr \left( S_{n}(i)\le s\right) }\cdot \Pr \left( X_{n+1}(i,z)\ge j\right) \\&\quad +\left[ 1-\sum _{z=1}^{s-1}\frac{\Pr \left( S_{n}(i)=z\right) }{\Pr \left( S_{n}(i)\le s\right) }\right] \Pr \left( X_{n+1}(i,s)\ge j\right) , \end{aligned}$$

By Assumption 3.3, $\Pr \left( X_{n+1}(i,z)\ge j\right)$ increases in z. Then,

$$\begin{aligned} \Pr \left( X_{n+1}(i,^{\le }(s+1))\ge j\right)&=\sum _{z=1}^{s+1}\frac{\Pr \left( S_{n}(i)=z\right) }{\Pr \left( S_{n}(i)\le s+1\right) }\cdot \Pr \left( X_{n+1}(i,z)\ge j\right) \\&\ge \sum _{z=1}^{s-1}\frac{\Pr \left( S_{n}(i)=z\right) }{\Pr \left( S_{n}(i)\le s+1\right) }\cdot \Pr \left( X_{n+1}(i,z)\ge j\right) \\&\quad \,+\left[ 1-\sum _{z=1}^{s-1}\frac{\Pr \left( S_{n}(i)=z\right) }{\Pr \left( S_{n}(i)\le s+1\right) }\right] \Pr \left( X_{n+1}(i,s)\ge j\right) . \end{aligned}$$

It follows that

$$\begin{aligned}&\Pr \left( X_{n+1}(i,^{\le }(s+1))\ge j\right) -\Pr \left( X_{n+1}(i,^{\le }s)\ge j\right) \\&\qquad \quad \ge -\sum _{z=1}^{s-1}\left[ \frac{\Pr \left( S_{n}(i)=z\right) }{\Pr \left( S_{n}(i)\le s\right) }-\frac{\Pr \left( S_{n}(i)=z\right) }{\Pr \left( S_{n}(i)\le s+1\right) }\right] \Pr \left( X_{n+1}(i,z)\ge j\right) \\&\quad \quad \quad \quad +\left[ \sum _{z=1}^{s-1}\frac{\Pr \left( S_{n}(i)=z\right) }{\Pr \left( S_{n}(i)\le s\right) }-\sum _{z=1}^{s-1}\frac{\Pr \left( S_{n}(i)=z\right) }{ \Pr \left( S_{n}(i)\le s+1\right) }\right] \Pr \left( X_{n+1}(i,s)\ge j\right) \\&\quad \quad \quad \ge -\sum _{z=1}^{s-1}\left[ \frac{\Pr \left( S_{n}(i)=z\right) }{\Pr \left( S_{n}(i)\le s\right) }-\frac{\Pr \left( S_{n}(i)=z\right) }{\Pr \left( S_{n}(i)\le s+1\right) }\right] \Pr \left( X_{n+1}(i,s)\ge j\right) \\&\quad \quad \quad \quad +\left[ \sum _{z=1}^{s-1}\frac{\Pr \left( S_{n}(i)=z\right) }{\Pr \left( S_{n}(i)\le s\right) }-\sum _{z=1}^{s-1}\frac{\Pr \left( S_{n}(i)=z\right) }{ \Pr \left( S_{n}(i)\le s+1\right) }\right] \Pr \left( X_{n+1}(i,s)\ge j\right) =0. \end{aligned}$$

Therefore, $\Pr \left( X_{n+1}(i,^{\le }s)\ge j\right)$ is increasing in s, implying that $X_{n+1}(i,^{\le }s)$ is stochastically increasing in s. $\square$

Appendix C: Proof of Proposition 3.1

Proof

By Lemma 3.1 and Assumption 3.4, we have $X_{n+1}(i+1,^{\le }s)\ge _{\text {st}}X_{n+1}(i+1,1)\ge _{\text {st} }X_{n+1}(i)\ge _{\text {st}}X_{n+1}(i,^{\le }z)$ for all s and z. The optimality Eqs. (4)–(5) can be solved by a value iteration process. Let $V_{0}(i,t)\equiv 0$ be the initial value function, $V_{m}(i,t)$ the value function generated by the mth value iteration for $m\ge 1$, and $J_{m}(i,t,\tau )$ the value of function $J(i,t,\tau )$ when V is replaced by $V_{m}$ in (5).

If we can prove $V_{m}(i,0)$ decreases in i for all $m\ge 0$, then $V(i,0)=\lim _{m\rightarrow \infty }V_{m}(i,0)$ also decreases in i. In the followings, we prove $V_{m}(i,0)$ decreases in i for all $m\ge 0$ by induction.

Suppose that $V_{m}(i,0)$ is decreasing in i. Note that

$$\begin{aligned}&\sum _{j\in {\mathcal {H}}}\Pr (X_{n+1} =j,S_{n}\le \tau \mid X_{n}=i)V_{m}(j,0) =\Pr \left( S_{n}\le \tau \mid X_{n}=i\right) \nonumber \\&\sum _{j\in {\mathcal {H}}}\Pr \left( X_{n+1}=j\mid S_{n}\le \tau ,X_{n}=i\right) V_{m}(j,0) \nonumber \\&\quad =\Pr \left( S_{n}\le \tau \mid X_{n}=i\right) E\left[ V_{m}\left( X_{n+1}(i,^{\le }\tau ),0\right) \right] . \text { Then,}\nonumber \\&\qquad J_{m}(i,0,\tilde{\tau })-J_{m}(i+1,0,\tau ) \nonumber \\&\quad =E\left\{ \min \left[ S_{n}(i),\tilde{\tau }\right] \right\} r(i)-E\left\{ \min \left[ S_{n}(i+1),\tau \right] \right\} r(i+1)\nonumber \\&\qquad +\Pr \left( S_{n}(i)>\tilde{\tau }\right) R(i)-\Pr \left( S_{n}(i+1)>\tau \right) R(i+1) \nonumber \\&\qquad +\Pr \left( S_{n}\le \tilde{\tau }\mid X_{n}=i\right) E\left[ V_{m}\left( X_{n+1}(i,^{\le }\tilde{\tau }),0\right) \right] \nonumber \\&\qquad -\Pr \left( S_{n}\le \tau \mid X_{n}=i+1\right) E\left[ V_{m}\left( X_{n+1}(i+1,^{\le }\tau ),0\right) \right] . \end{aligned}$$

(7)

By the inductive hypothesis that $V_{m}(i,0)$ decreases in i, and the fact that $X_{n+1}(i+1,^{\le }s)\ge _{st}X_{n+1}(i,^{\le }z)$ for all s and z, for each $i\in {\mathcal {H}}$ there exists a(i) such that $E\left[ V_{m}\left( X_{n+1}(i+1,^{\le }\tau ),0\right) \right] \le a(i)\le E\left[ V_{m}\left( X_{n+1}(i,^{\le }\tilde{\tau }),0\right) \right]$ for all $\tilde{\tau }\ge 0$ and $\tau \ge 0$.

For an arbitrary $\tau$, let us select $\tilde{\tau }$ such that $F_{S_{n}(i)}(\tilde{\tau })\le F_{S_{n}(i+1)}(\tau )\le F_{S_{n}(i)}(\tilde{ \tau }+1)$.

If $R(i)\ge a(i)$, by (7) and the condition $R(i)\ge R(i+1)$ , then

$$\begin{aligned} J_{m}(i,0,\tilde{\tau })-J_{m}(i+1,0,\tau )\ge \left[ R(i)-a(i)\right] \left[ F_{S_{n}(i+1)}(\tau )-F_{S_{n}(i)}(\tilde{\tau })\right] \ge 0. \end{aligned}$$

Otherwise, $R(i+1)\le R(i)<a(i)$. We can replace $\tilde{\tau }$ with $\tilde{\tau }+1$ in (7) and obtain

$$\begin{aligned}&J_{m}(i,0,\tilde{\tau }+1)-J_{m}(i+1,0,\tau )\\&\quad \ge \left[ a(i)-R(i+1)\right] \left[ F_{S_{n}(i)}(\tilde{\tau }+1)-F_{S_{n}(i+1)}(\tau )\right] \ge 0. \end{aligned}$$

Finally, $V_{m+1}(i,0)=\max _{\tau \ge 0}J_{m}(i,0,\tau )\ge \max \left\{ J_{m}(i,0, \tilde{\tau }),J_{m}(i,0,\tilde{\tau }+1)\right\} \ge J_{m}(i+1,0,\tau )$. Taking maximization with respect to $\tau$ causes $V_{m+1}(i,0)\ge V_{m+1}(i+1,0)$, proving the monotonicity of $V_{m+1}(i,0)$ in i. $\square$

Appendix D: Proof of Lemma 3.2

Proof

It is easy to see that the following three equalities hold

$$\begin{aligned}&E\left[ \min (S_{n},\tau +1)\mid X_{n}=i,S_{n}>t\right] -E\left[ \min (S_{n},\tau )\mid X_{n}=i,S_{n}>t\right] \\&\quad =\Pr \left( S_{n}>\tau \mid X_{n}=i,S_{n}>t\right) , \\&\Pr \left( S_{n}>\tau +1\mid X_{n}=i,S_{n}>t\right) -\Pr \left( S_{n}>\tau \mid X_{n}=i,S_{n}>t\right) \\&\quad =-\Pr \left( S_{n}=\tau +1\mid X_{n}=i,S_{n}>t\right) ,\\&\text {and }\Pr \left( X_{n+1}=j,S_{n}\le \tau +1\mid X_{n}=i,S_{n}>t\right) \\&\quad \quad -\Pr \left( X_{n+1}=j,S_{n}\le \tau \mid X_{n}=i,S_{n}>t\right) \\&\quad =\Pr \left( X_{n+1}=j,S_{n}=\tau +1\mid X_{n}=i,S_{n}>t\right) . \end{aligned}$$

By (5) and the definition of conditional probability, we have

$$\begin{aligned}&J(i,t,\tau +1)-J(i,t,\tau ) \nonumber \\&\quad =\frac{\Pr (S_{n}>\tau \mid X_{n}=i)}{\Pr (S_{n}>t\mid X_{n}=i)}r(i)-\frac{ \Pr (S_{n}=\tau +1\mid X_{n}=i)}{\Pr (S_{n}>t\mid X_{n}=i)}R(i) \nonumber \\&\qquad +\sum _{j\in {\mathcal {H}}}\frac{\Pr (X_{n+1}=j,S_{n}=\tau +1\mid X_{n}=i)}{ \Pr (S_{n}>t\mid X_{n}=i)}V(j,0) \nonumber \\&\quad =\frac{\Pr (S_{n}>\tau \mid X_{n}=i)}{\Pr (S_{n}>t\mid X_{n}=i)} \nonumber \\&\qquad \cdot \left[ r(i)-R(i)H_{i}(\tau )+\sum _{j\in {\mathcal {H}}}\Pr \left( X_{n+1}=j,S_{n}=\tau +1\mid X_{n}=i,S_{n}>\tau \right) V(j,0)\right] \nonumber \\&\quad =\frac{\Pr (S_{n}(i)>\tau )}{\Pr (S_{n}(i)>t)}H_{i}(\tau )\left[ \frac{r(i) }{H_{i}(\tau )}-R(i)+\sum _{j\in {\mathcal {H}}}\gamma _{ij}(\tau +1)V(j,0) \right] , \end{aligned}$$

(8)

where the function $\gamma _{ij}$ is defined as $\gamma _{ij}(t):=\Pr \left( X_{n+1}=j\mid X_{n}=i,S_{n}=t\right)$ and the last equality holds because

$$\begin{aligned}&\frac{\Pr \left( X_{n+1}=j,S_{n}=\tau +1\mid X_{n}=i,S_{n}>\tau \right) }{ H_{i}(\tau )}&\\&\quad =\frac{\Pr \left( X_{n+1}=j,S_{n}=\tau +1\mid X_{n}=i,S_{n}>\tau \right) }{\Pr \left( S_{n}=\tau +1\mid X_{n}=i,S_{n}>\tau \right) } \\&\\&\quad =\Pr \left( X_{n+1}=j\mid X_{n}=i,S_{n}=\tau +1\right) =\gamma _{ij}(\tau +1). \end{aligned}$$

Moreover, $\sum _{j\in {\mathcal {H}}}\gamma _{ij}(\tau +1)V(j,0)=E\left[ V\left( X_{n+1}(i,\tau +1),0\right) \right]$ is decreasing in $\tau$, according to Assumption 3.3 and the fact that V(i, 0) decreases in i. Let $u(i,\tau )=\frac{r(i)}{H_{i}(\tau )}-R(i)+\sum _{j\in {\mathcal {H}}}\gamma _{ij}(\tau +1)V(j,0)$. Then, $u(i,\tau )$ is decreasing in $\tau$. Let $\tau ^{*}(i)=\min \left\{ \tau \ge 0\mid u(i,\tau )\le 0\right\}$. Based on the above analysis, we can conclude that $J(i,t,\tau +1)-J(i,t,\tau )>0$ for $\tau <\tau ^{*}(i)$, and $J(i,t,\tau +1)-J(i,t,\tau )\le 0$ for $\tau \ge \tau ^{*}(i)$. This proves the quasi-concavity of $J(i,t,\tau )$ with respect to $\tau$. $\square$