\section{Introduction and Examples}  \label{sec:intro}


\subsection{The Problem}
Consider the following quickest detection optimal sampling problem which is a special case of the problem considered
in this paper.
 Let $\tau_k, k=0,1,\ldots$ denote the time
 instants at which decisions to observe a noisy finite state Markov chain are made.
   As it accumulates measurements over time,
  a decision-maker needs to announce when   the Markov chain hits a specific absorbing target state. 
 
 
At each decision time  $\tau_k$, the decision maker needs to pick its decision from the action set  $\mathcal{U} =\{0 \text{ (announce change)} ,\D_1,\D_2,\ldots,\D_L\}$ where
 \begin{compactitem}
\item  Decision $u_{k}=0$ made at time $\tau_k$ corresponds to ``{\em announce the target state and stop}''. When this decision is made the problem terminates at time $\tau_k$ with possibly a  false alarm penalty (if the Markov chain was not in the target state).
\item  Decision $u_{k} \in \{\D_1,\D_2,\ldots,\D_L\}$ at time $\tau_k$  corresponds to:
``{\em Look at noisy Markov chain next at time $\tau_{k+1} = \tau_k + u_k$.}" Here 
$D_1 < D_2 < \cdots < D_L$ are fixed positive integers. They denote the set of possible time delays to  sample the Markov chain next.
\end{compactitem}
Given the  history  of past measurements and  decisions, 
how should the decision-maker choose its decisions $u$? Let $t^*$ denote the time at which the Markov chain hits
that the absorbing target state and $k^*$ denote the time at which the decision maker announces that the Markov chain has hit 
the target state.
The decision-maker considers the following costs:\\
(i) {\em False alarm penalty}: If $k^* < t^*$, i.e., the Markov  chain is not in the target state, but the decision-maker announces that the chain
has hit the target state, it pays a false alarm penalty ${f}$.\\
(ii) {\em Delay penalty}: If $k^*  > t^*$, i.e.,  the Markov chain hits the target state and the decision-maker does not announce this, it pays a delay penalty $d$.
The decision maker continues to pay this delay penalty over time until it announces the target state has been reached.
\\
(iii) {\em Sampling cost}: At each  decision time $\tau_k$, the decision maker  looks at the noisy Markov chain and
 pays a measurement (sampling) cost $m$.
 
 Suppose the Markov chain starts with initial distribution $\pi_0$ at time $0$.
  {\em What is the optimal sampling strategy $\mu^*$ for the decision-maker
 to minimize  the following  combination of the false alarm rate, delay penalty and measurement cost?} 
That is, determine $\mu^* = \inf_\mu J_\mu(\pi_0) $ where
 \begin{equation} J_\mu(\pi_0) =   d \E^\mu_{\pi_0}\{(k^* - t^*)^+\} + {f}\, \P^\mu_{\pi_0}(k^* < t^*)  +
 m \sum_{u=1}^L \sum_{k:\tau_k \leq k^*} \P^\mu_{\pi_0}(u_k = u)
\label{eq:ksintro}
\end{equation}
Here $\mu$ denotes a  stationary strategy of  the decision maker.  $\P^\mu$ and $\E^\mu_{\pi_0}$ are the probability measure and expectation
of the evolution of the observations and Markov state which are strategy dependent (These are defined formally
in Sec.\ref{sec:qdbasic}).
 Taking  frequent measurements yields accurate estimates but incurs a higher measurement cost. Making an erroneous decision too soon incurs a false alarm penalty. Waiting too long to declare the target state
incurs a delay penalty.


 \subsection{Context}
In the special case  when the change time $t^*$ is 
geometrically-distributed (equivalently, the Markov chain has two states), action space
$\mathcal{U} = \{0 \text{ (announce change)},1 \text{ (continue)}\}$, measurement cost $m = 0$, then (\ref{eq:ksintro}) 
becomes the classical Kolmogorov--Shiryayev
 quickest detection problem \cite{Shi78,PH08}.
Our setup generalizes this  in the following non-trivial ways:\\
First, unlike quickest detection, there are now multiple
``continue" actions  $u\in \{1,2,\ldots,L\}$ corresponding to different sampling  delays  $\{\D_1,\D_2,\ldots,\D_L\}$. (In quickest detection there is only one continue action and one stop action).
Each of these ``continue'' actions  result
in different dynamics of the posterior distribution and incur different costs. Also, the measurement costs
can be state and action dependent. 
\\
  Second, allowing for the underlying Markov chain to have multiple states  facilitates 
modelling general phase-distributed (PH-distributed) change times
(compared to two state Markov chains that model geometric distributed change times).
As described in \cite{Neu89}, a PH-distributed change time can be modelled
as a multi-state Markov chain with an absorbing state.  The optimal detection of a PH-distributed change point is useful  since  PH-distributions form a dense subset for the set of all distributions; see \cite{Kri11} for quickest detection 
with PH-distributed change times.

  
  
  
  
  
\subsection{Main Results, Organization and Related Works}
This paper analyzes the structure of the optimal sampling strategy of the decision-maker.
 The problem is an instance of a 
partially observed Markov decision process (POMDP) \cite{Cas98}.
   In general, solving POMDPs and therefore determining the optimal strategy is computationally intractable (PSPACE hard \cite{PT87}). 
  However, returning to the example considered above,
intuition suggests that the following  strategy would be sensible  (recall that the action set  $\mathcal{U} =\{0 \text{ (announce change)} ,\D_1,\D_2,\ldots,\D_L\}$):
\begin{compactitem}
\item If the Bayesian posterior distribution estimate of the Markov chain (given past observations and decisions) is away from the target state,  look infrequently at the noisy Markov chain. i.e., pick a large sampling interval $D_u$. Since we are interested in detecting when the Markov chain
hits the target state, there is little point in incurring a measurement cost by looking at the Markov chain when its estimate suggests that it is far away from the target state.
\item If the posterior distribution is close to the target state, then pay a higher sampling cost and look more frequently at the 
noisy Markov chain, i.e., pick a small sampling interval
$D_u$.
\item If the posterior is sufficiently close to the
 target state, then announce the target state has been reached, i.e., choose action $u=0$.
\end{compactitem}
The key point is that such a strategy (choice of sampling interval $D_u$) is monotonically decreasing as the posterior distribution gets closer to the target state.
By using  stochastic dominance and   lattice programming analysis,
   this paper shows that under reasonable conditions, the optimal sampling strategy always has this monotone structure.
 
  Lattice programming was championed by \cite{Top98} and provides a  general set of sufficient conditions for the existence
of monotone strategies in stochastic control problems.  This area falls under the general
umbrella of monotone comparative statics that has witnessed remarkable interest in the area of economics \cite{Ath02}.
Our results  apply to general observation distributions (Gaussians, exponentials, Markov modulated Poisson, discrete
memoryless channels, etc) and multi-state Markov chains.

In  more detail, this paper  establishes the following structural results:
\\
{\bf (i)} For  two-state Markov chains  observed in noise,  since the elements of the two-dimensional posterior probability mass function add to 1, 
 it suffices to consider one element  of this posterior -- this element is a probability and lies in the interval $[0,1]$.
Theorems~\ref{thm:main1} and \ref{cor:qd} show that under reasonable conditions
the optimal sampling strategy of the decision-maker has a monotone structure in the posterior distribution.
The monotone structure of  Theorem~\ref{thm:main1} reduces
a function space optimization problem  (dynamic programming on the space of posterior distributions) to a finite dimensional optimization -- 
since a monotone strategy  with $L$ possible actions has at most $L-1$ thresholds in the space of posterior distributions.
The threshold values  can be estimated via simulation based stochastic approximation.
The  monotone structure holds even for large delay penalty and measurement cost that is 
 independent of the state.
  If satisfaction is viewed as the number of times the decision maker looks at the Markov chain, 
  Theorems~\ref{thm:main1} and \ref{cor:qd}    say that ``delayed satisfaction" is optimal. These theorems also directly apply to a measurement
  control model recently developed in \cite{BV12} as will be discussed in Sec.\ref{sec:geom}.
  \\
{\bf (ii)}  For general-state Markov chains (which can model PH-distributed change times) observed in noise,  
the posterior lies in a $X-1$ dimensional unit simplex.
Theorem \ref{thm:myopic} shows that the optimal decision-maker's sampling strategy can be under-bounded by a 
judiciously chosen myopic strategy on the unit simplex of posterior distributions. Therefore the myopic strategy forms an easily
computable rigorous lower bound
to the optimal strategy. Sufficient conditions are given for the myopic strategy to have a monotone structure with respect
to the monotone likelihood ratio stochastic order on the simplex.
Theorem \ref{cor:qd2} illustrates the result for quickest detection problems.\\
{\bf (iii)} 
How does the  optimal expected  sampling cost  vary
  with
 transition matrix and noise distribution?  Is it possible to order   these parameters
 such that the larger they are, the larger the optimal sampling cost? Such a result would allow us to compare the optimal
 performance of different sampling models, even though computing these is intractable
For general-state Markov chains  observed in noise, Theorem~\ref{thm:tmove}  examines how the cost achieved by the optimal sampling strategy varies with
 transition matrix (state dynamics) and observation matrix (noise distribution). In particular  dominance measures are introduced
 for the transition matrix and observation distribution (Blackwell dominance) that result in the optimal cost increasing with respect
 to this dominance order. Theorem~\ref{thm:tmove}  shows that  for  optimal sampling 
problems, certain PH-distributions for the change time result in larger total optimal cost compared to other 
distributions.
\\
{\bf  (iv)}  Theorem \ref{thm:sens} derives  sensitivity bounds on the total cost for optimal sampling with
 a mis-matched model. That is, when the optimal strategy computed for a specific sampling model is used for a different
 sampling model, Theorem \ref{thm:sens} gives an explicit bound on the performance degradation.  In particular, by elementary use
 of the Pinsker inequality \cite{CT06},  Theorem \ref{thm:sens} shows that the sensitivity is a linear function  of the Kullback-Leibler divergence between the two models.
 Also, the bounds are tight in the sense
 that if the difference between the two models goes to zero, so does the performance degradation.
 \\
{\bf  (v)} To prove the above results, several important stochastic dominance properties of the Bayesian filter are presented in Theorem \ref{thm:filter}. How does the posterior distribution computed by the Bayesian filter vary with observation, prior, transition matrix
and observation matrix? Is it possible to order these so that the posterior distribution increases with respect to this ordering?
 These results are of independent interest.
 The theorem gives sufficient conditions for the Bayesian filtering recursion to preserves the MLR (monotone likelihood ratio)
 stochastic order, and for the normalization measure to be  submodular. It also shows  that if starting with two different transition matrices but identical priors, then the optimal predictor with the larger transition matrix
 (in terms of the order introduced in (\ref{eq:mor})) MLR dominates the predictor with the smaller transition matrix.
 


{\em Related Works}: In this paper we consider sampling control with change detection. A related problem is measurement control where
at each time the decision is made  whether to take a measurement
or not. This is the subject of the recent paper\footnote{The author is very grateful to Dr.\ Venu Veeravalli of U.\ Illinois Urbana Champaign
for sharing the results in \cite{BV12} and several useful discussions}  \cite{BV12} which considers geometric-distributed change times (2-state Markov chain).
The problem in \cite{BV12} can be formulated in terms of  our optimal sampling problem. 
 We discuss this further in Sec.\ref{sec:2state}. 

We also refer to the seminal work of Moustakides (see \cite{YMW12} and references therein) in event triggered sampling. 
Quickest detection has been studied widely, see \cite{PH08,TV05} and references therein.
We have considered recently  a POMDP approach to quickest detection with social learning \cite{Kri12} and non-linear penalties \cite{Kri11} 
and phase-distributed change times. However,
in these papers, there is only one continue and one stop action. The results in the current paper are considerably more general due
to the propagation of different dynamics for the multiple continue actions. A useful feature of the lattice programming approach  \cite{Alb79,Lov87,Rie91}
used in this paper is that the results apply to general observation noise distributions (Gaussians, exponentials, discrete
memoryless channels)  and multiple state Markov chains. Also,  the results proved here are valid for finite sample
sizes and no asymptotic approximations in signal to noise ratio are used. 


\subsection{Examples: Change Detection and Sensor Scheduling} 
Several examples in statistical signal processing are special cases of the above measurement-sampling control model.  The terms active/smart/cognitive  
sensing imply the use of feedback of previous estimates and decisions to choose the current optimal decision. 

{\em Example 1. Quickest Time Change Detection with Optimal Sampling}:
Return to the problem  considered at the beginning of this section. The action space is $\{0 \text{ (announce change)}, D_1=1,D_2=3,D_3=5,D_4=10\}$.
That is, at each decision time, the decision  maker has the option of either stopping  or looking at a 2-state Markov chain every 1, 3, 5 or 10
time points.
 Suppose the decision maker observes the underlying Markov chain
via a binary erasure channel (parameters values are specified in Sec.\ref{sec:numerical}).

Theorem \ref{thm:main1} shows
that
 the optimal strategy has a monotone structure in posterior $\pi(1)$ depicted in 
Figure \ref{fig:thm1}(a).
   The horizontal axis in Figure \ref{fig:thm1}(a) denotes the Bayesian
 posterior $\pi(1)$  while the vertical axis denotes the optimal action taken. 
Therefore, when the posterior is less than $\pi_4^*$, it is optimal to look every 10 time points at the noisy Markov chain, for posterior in the interval $[\pi_4^*,\pi_3^*]$
look every 5 points at the noisy Markov chain, etc.
 Thus one only needs to compute/estimate the threshold values $\pi_1^*, \pi_2^*, \pi_3^*,\pi_4^*$ to determine the optimal strategy.
  The usefulness of Theorem \ref{thm:main1} 
 is further enhanced by noting
that  in general (without introducing conditions) the optimal strategy does not have this property.
Figure \ref{fig:thm1}(b) gives an example where
 the sufficient conditions of Theorem \ref{thm:main1} are violated and
  the optimal strategy is no longer monotone.


\begin{figure}\centering
\mbox{\subfigure[Structured Strategy]{\epsfig{figure=fig1.eps,width=0.35\linewidth} } \quad
\subfigure[Unstructured Strategy]{\epsfig{figure=fig2.eps,width=0.35\linewidth} }}
\caption{Optimal sampling strategy $\mu^*(\pi)$ for action space $u\in \{ 0 \text{ (announce change) }, D_1=1,D_2=3,\;D_3=5,\;D_4=10\}$ for a quickest-change detection
problem with geometric change time.  The noisy observations are from
a binary erasure channel and the parameters are specified in Example 1 of Sec.\ref{sec:numerical}.
 Figure
 \ref{fig:thm1}(a) depicts a monotone decreasing optimal strategy in posterior $\pi(1)$. Theorem \ref{thm:main1} gives sufficient conditions under which 
 the optimal sampling strategy $\mu^*(\pi)$ has this structure. The threshold
values  $\pi_1^*,\pi_2^*,\pi_3^*,\pi_4^*$ give a finite dimensional characterization of the optimal strategy.
Fig.\ref{fig:thm1}(b) gives an example where  the conditions of Theorem \ref{thm:main1} are violated
and the optimal strategy is no longer monotone in $\pi(1)$.}
\label{fig:thm1}
\end{figure}

\begin{comment}
{\em Example 2. Decision making with delayed satisfaction}: A related problem that we will also analyze in this paper is sequential decision
making with ``delayed satisfaction''. 
 Even though the setup is different, the structural results given in this paper apply to this problem. Let us briefly
describe this problem.
  At each decision interval $\tau_k$, a delayed measurement is made of the state at time $k- u_k$ where as before, $u_k \in \{\D_1,\D_2,\ldots,\D_L\}$ denotes the set of possible delays.
If one is willing to get a measurement with a larger delay, the cost of acquiring the measurement is typically smaller. As in the
formulation above, the aim is to determine the optimal choice of $u_k$ at each time to minimize a combination of false alarm, delay penalty and measurement cost. \end{comment}

{\em Example 2. Sensor Measurement Scheduling}: 
In  sensor and radar resource management problems, the sensor is a resource that needs
to be allocated amongst several targets \cite{Kri02,KD07}. Deploying a sensor to  look at a target consumes sensor resources. How should a sensor scheduler
 decide how often to look at a target in order to detect if the target has made a sudden maneuver (modelled by the Markov chain
 jumping to a target state)? In radar resource management
 \cite{KBGM12} this is called the revisit time problem.
 

  
\section{Formulation of Optimal Sampling Problem} \label{sec:qdbasic}



 Let $\time = 0,1,\ldots$ denote discrete time and 
$x_\time$  denote
a Markov chain on
the finite state space 
\begin{equation}  \{e_1,\ldots,e_X\} \text{  where $e_i$ is the $X$-dimensional unit vector with 1 in the $i$-th position}. \label{eq:ei}\end{equation}
 Here  state `1'  (corresponding to $e_1$) is labelled as the ``target state''. 
  Denote
\begin{equation} 
\mathbb{X} = \{1,2,\ldots,X\}
. \end{equation}
Denote $X\times X$ 
transition probability matrix $A$  and the $X\times 1$ initial distribution $\pi_0$ where
\begin{equation} A=(A_{ij},i,j\in \mathbb{X}), \; A_{ij} = P(x_{\time+1}=e_j|x_\time=e_i), \quad \pi_0 = (\pi_0(i), i \in \mathbb{X}),\;  \pi_0(i) = 
P(x_0 = e_i).\label{eq:init} \end{equation}

\subsection{Measurement Sampling Protocol} \label{sec:qdmodel}

  Let  $\tau_1,\ldots,\tau_{k-1}$ denote previous discrete time instants at which measurement
samples  were taken.
Let $\tau_k$ denote the current time-instant at which a measurement is taken. The measurement sampling protocol proceeds according to the  following
steps:


 {\em Step 1. Observation}: A noisy measurement $y_k \in \mathbf{Y}$ at time $\tau_k$  of the Markov chain is  obtained with
conditional probability distribution
 \begin{equation} \label{eq:obs}
 P(y_{k} \leq \bar{y}|x_{\tau_k} = e_x) = \sum_{y\leq \bar{y}} B_{xy},\quad x \in  \mathbb{X} \end{equation}
Here $\sum_y$ denotes integration with respect to the Lebesgue measure
(in which case $\mathbf{Y}\subset \mathbb{R}$ and $B_{xy}$ is the conditional probability density function)
or counting measure (in which case $\mathbf{Y}$ is a subset of the integers and $B_{xy}$ is the conditional probability
mass function $B_{xy}= P(y_{k}=y|x_{\tau_k}=e_x)$).
 

{\em  Step 2. Sequential Decision Making}:  
Denote the filtration generated by  measurements and past decisions (denoted $u_1,\ldots,u_{k-1}$) as
  \begin{equation}
  \label{eq:sigf} \mathcal{F}_k = \text{ $\sigma$-algebra generated by } (y_{1},\ldots,y_{k},u_1,\ldots,u_{{k-1}}). \end{equation}
 At time $\tau_k$, a $\mathcal{F}_k$ measurable decision $u_k \in \mathcal{U} $ is taken
where action
\begin{align}  \label{eq:actionstrategya}
 u_{k} &= \mu(\mathcal{F}_k)  \in \mathcal{U} = \{0 \text{ (announce change)} ,1,2,\ldots, L\} \\
  \text{ and } & u_k = l \text{ denotes:  obtain next measurement after } D_l \text{ time points}, l \in \{1,2,\ldots,L\} . \nonumber
 \end{align}
In (\ref{eq:actionstrategya}),  the strategy $\mu$  belongs to the class of stationary decision
strategies denoted $\boldsymbol{\mu}$. Also, $D_1,\ldots,D_L$ are distinct positive integers that denote the set of possible sampling time intervals.
Thus the  decision $u_{k}$ specifies the next time $\tau_{k+1}$ to make a measurement as follows:
\begin{equation}
\tau_{k+1} = \tau_k  + D_{u_{k}} , \quad u_k \in \{1,2,\ldots,L\}.\end{equation}

{\em Step 3. Costs}:
Associated with the decision $u_{k} \in \mathcal{U}$, a  cost 
$c(x_t,u_{k})$ is incurred by the decision-maker at each time $\time \in [\tau_k,\ldots,\tau_{k+1}-1]$ until the next measurement is taken at time $\tau_k$. Also a non-negative measurement sampling cost    $m(x_{\tau_k},u_{k})$ is incurred.


{\em Step 4}: If $u_{k}  = 1$, the problem terminates, else 
set $k$ to $k+1$ and go to Step 1.  \qed \\




\subsubsection*{Belief State Formulation} It is convenient to re-express Step 2 of the above protocol
in terms of the belief state.  It is well known from elementary stochastic control \cite{Lov87} that the belief state
(posterior) constitutes a sufficient statistic for $\mathcal{F}_k$ in (\ref{eq:sigf}).
Denote the belief state as $\pi_k = \E\{x_{\tau_k}|\mathcal{F}_k\}$. Since the state space (\ref{eq:ei}) comprises of unit indicator vectors, conditional
probabilities and conditional expectations coincide. So
\begin{equation}   \pi_k = (\pi_k(i), \, i \in \mathbb{X}) \text{ where } \pi_k(i) = P(x_{\tau_k} = e_i|y_{1},\ldots,y_{k},u_{1},\ldots,u_{{k-1}}), \text{ initialized by } \pi_0.
\end{equation}
It is easily proved that the belief state
 is updated via the Bayesian (Hidden Markov Model) filter 
\begin{align}  \label{eq:hmm} \pi_k &= T(\pi_{k-1},y_k,u_{k-1}),  \text{ where }
T(\pi,y,u) =
\frac{B_y ({A^{\prime}})^{D_u}\pi}{\sigma(\pi,y,u)},
\; \sigma(\pi,y, u) = \mathbf{1}_X^\prime B_y  ({A^\prime})^{D_u} \pi
\\
B_y &= \text{diag}(P(y|x),x\in \mathbb{X}).  \nonumber
 \end{align}
 Here $\sigma(\pi,y,u)$ is the normalization measure of the Bayesian update with $\sum_y \sigma(\pi,y,u) = 1$. Also
  $\mathbf{1}_X$ denotes the $X$ dimensional vector of ones.
Note that  $\pi$ in (\ref{eq:hmm})  is an $X$-dimensional probability vector. It belongs to the
 $X-1$ dimensional unit-simplex denoted as
\begin{align}
\Pi(X) \stackrel{\triangle}{=} \left\{\pi \in \mathbb{R}^{X}: \mathbf{1}_X^{\prime} \pi = 1,
\quad 
0 \leq \pi(i) \leq 1 \text{ for all } i \in \mathbb{X} \right\} \label{eq:Pi}
\end{align}
For example, $\Pi(2)$ is a one dimensional simplex (unit line segment),
$\Pi(3)$ is a two-dimensional  simplex (equilateral triangle); $\Pi(4)$
is a tetrahedron, etc.
Note that the unit vector states  $e_1,e_2,\ldots, e_X$ defined in (\ref{eq:ei}) of the Markov chain $x$ are the vertices of $\Pi(X)$.

Step 2 in the above protocol expressed in terms of the belief state reads: At decision time $\tau_k$
\begin{itemize}
\item {\em Step 2(a)}. Update belief state $\pi_k$ according to Bayesian filter  (\ref{eq:hmm}) 
\item {\em Step 2(b)}. Make decision $u_k \in \mathcal{U}$ using stationary strategy $\mu$ as (see (\ref{eq:actionstrategya}))
\begin{equation} \label{eq:actionstrategy}
 u_{k} = \mu(\pi_k)  \in \mathcal{U} = \{0 \text{ (announce change)} ,1,2,\ldots, L\}. \end{equation}
\end{itemize}




\subsection{Sequential Decision-maker's Objective and Stochastic Dynamic Programming} Given the above protocol with measurement-sampling strategy $\mu$ in (\ref{eq:actionstrategy}), we now
define the objective of the sequential decision maker.
Let $(\Omega,\mathcal{F})$ be the underlying measurable space where $\Omega = (\mathbb{X} \times \mathcal{U} \times \mathbf{Y})^\infty$ is the product space, which is endowed with the product topology and $\mathcal{F}$  is the corresponding product sigma-algebra. For any $\pi_0\in \Pi(X)$,  and strategy $\mu \in \boldsymbol{\mu}$,
 there exists a (unique) probability measure $\P^\mu_{\pi_0}$ on  $(\Omega, \mathcal{F})$,
   see 
 \cite{HL96} for details. Let $\E^\mu_{\pi_0}$  denote the expectation with respect to the measure  $\P^\mu_{\pi_0}$.
 
Define the  $\{\mathcal{F}_k,k\geq 1\}$ measurable stopping time $k^*$
as
\begin{equation}
k^* = \{ \inf k:  u_k = 0 \text{ (announce target state and stop) } \} .   \label{eq:kstar}\end{equation}
That is, $k^*$ is the time at which the decision maker declares the target state has been reached and the problem terminates.
 For each initial distribution $\pi_0 \in \Pi(X)$, and strategy
 $\mu$, the decision maker's global objective function is
 \begin{equation}
 J_\mu(\pi_0) = \E^\mu_{\pi_0}\left\{\sum_{k=1}^{k^*-1}  
\left[m(x_{\tau_k},u_k) + 
 \sum_{\time = \tau_k}^{\tau_{k+1}-1}
c(x_t,u_k) \right]
+ c(x_{{\tau_{k^*}}}, u_{{k^*}})
 \right\} \label{eq:rawcost}
 \end{equation}
  Recall that $c(x,u)$ and measurement sampling cost $m(x,u)$ are defined in Step 3 of the protocol.
 Using the smoothing property of conditional expectations, (\ref{eq:rawcost}) can be expressed in terms of the belief state $\pi$ as
\begin{align}
 J_\mu(\pi_0) &= \E^\mu_{\pi_0}\left\{\sum_{k=1}^{k^*-1}  C(\pi_{k},u_{k}) 
+C(\pi_{{{k^*}}}, u_{{k^*}}=0)
 \right\}   \label{eq:cost}\\
\text{ where }  C(\pi,u) &=  C_u ^\prime \pi  \text{ for } u \in \mathcal{U}, \; \text{ and the $X$-dimensional cost vector $C_u$ is } \nonumber \\
C_0 &=  \begin{bmatrix}c(e_1,0),\ldots,c(e_X,0)\end{bmatrix}^\prime , \nonumber\\  C_u &=
m_u + (I+ A + \cdots + A^{D_u-1}) c_u \text{ for } u \in \{1,2,\ldots,L\},\nonumber\\
 c_u &= \begin{bmatrix}c(e_1,u),\ldots,c(e_X,u)\end{bmatrix}^\prime, \quad
m_u = \begin{bmatrix} m(e_1,u),\ldots, m(e_X,u) \end{bmatrix}^\prime .
\nonumber
 \end{align}

 
The decision-maker aims to determine the  optimal strategy $\mu^* \in \boldsymbol{\mu}$ to minimize (\ref{eq:cost}),
i.e., 
\begin{equation} \label{eq:mustar}
 J_{\mu^*}(\pi_0) = \inf_{\mu \in \boldsymbol{\mu}} J_\mu(\pi_0) .\end{equation} The existence of an optimal stationary strategy $\mu^*$ follows from \cite[Prop.1.3, Chapter 3]{Ber00b}.


Considering  the  global objective  (\ref{eq:cost}),
the optimal stationary strategy $\mu^*: \Pi(X) \rightarrow \mathcal{U}$ and associated optimal objective $J_{\mu^*}(\pi)$ are the solution of the following
 ``Bellman's stochastic dynamic programming  equation'' 
\begin{align} \label{eq:dp_alg}
\mu^*(\pi)&= \arg\min_{u \in \mathcal{U}} Q(\pi,u) , \;J_{\mu^*}(\pi) = V(\pi) = \min_{u \in \mathcal{U}} Q(\pi,u),\\
 \text{ where }  Q(\pi,u) &=  C(\pi,u)
+ \sum_{y \in \mathbf{Y}}  V\left( T(\pi ,y,u) \right) \sigma(\pi,y,u),\; u =1 ,\ldots,L, \quad
Q(\pi,0) =  C(\pi,0).
 
  \nonumber
\end{align}
Recall $T(\pi,y,u)$ and  $\sigma(\pi,y,u)$ were defined in (\ref{eq:hmm}).
The above formulation is a generalization of a  partially observed Markov decision process (POMDP), since  POMDPs assume
finite observations spaces $\mathbf{Y}$ while in our formulation $\mathbf{Y}$ can be discrete or continuous (see  (\ref{eq:obs})).

Define the   set of belief states where it is optimal to apply action $u=0$ as \begin{multline} 
\mathcal{S} =  \{\pi \in \Pi(X) : \mu^*(\pi) = 0\} = \{\pi \in \Pi(X):Q(\pi,0) \leq Q(\pi,u),
 \; u \in \{1,2,\ldots,L\} \} 
 \label{eq:stopset}
 \end{multline}
$\mathcal{S}$ is called the {\em stopping set} since it is the set of belief states to ``declare  target state and stop''. 

Since the belief state space $\Pi(X)$ is an uncountable, Bellman's equation (\ref{eq:dp_alg}) does not translate directly  into 
numerical algorithms. However,  in subsequent sections, we exploit the
structure of Bellman's equation
 to prove various structural results about the optimal strategy $\mu^*$ using lattice programming and stochastic dominance tools.

\begin{comment}
\noindent {\em Value Iteration Algorithm and methodology}:
The   value iteration
algorithm  presented in Appendix~\ref{sec:vi} is  a fixed point iteration of 
Bellman's equation. Since the belief state space $\Pi(X)$ is an uncountable  set, the
value iteration algorithm (\ref{eq:vi}) is not useful from a computational point of view
since
$V_k(\pi) $ needs to be evaluated at each $\pi \in \Pi(X)$, an
uncountable set.
However,  in subsequent sections, we exploit the
structure of the value iteration 
recursion to prove various structural results about the optimal strategy $\mu^*$ via mathematical induction.
As described in Appendix \ref{sec:vi}, the value iteration algorithm  generates a sequence of value functions
$\{V_k\}$  that will converge uniformly (sup-norm metric) as $k\rightarrow \infty$ to $V(\pi)$, the optimal value
 function of Bellman's equation.  

\end{comment}



\subsection{Example: Quickest Change Detection with Measurement Control} \label{sec:exqd}
We now formulate the quickest detection problem with optimal sampling -- this serves as a useful example to illustrate
 the above general model.
Before proceeding, it is important to recall  that in our  model, decisions (whether to stop, or continue and take next observation sample
after $D_l$ time points) are made at times $\tau_1,\tau_2, \ldots$. In contrast,  the state of the Markov chain  (which models the change
we want to detect) can change
at any time $t$. We need to construct the  delay penalty and false alarm penalties carefully
to   take this into account. 
\\
1.  {\em Phase-Distributed (PH) Change time}:  In quickest detection, the target state (which we label as state 1 by convention) is an absorbing state.
States $2,\ldots,X$ (corresponding to unit vectors $e_2,\ldots,e_X$) are now  fictitious states that form  a single composite state that 
the Markov chain $x_t$ resides in before jumping into the target absorbing state.
So the transition matrix (\ref{eq:init})  is
\begin{equation} \label{eq:phmatrix}
A = \begin{bmatrix}  1 & 0 \\ \underline{A}_{(X-1)\times 1} & \bar{A}_{(X-1)\times (X-1)} \end{bmatrix}.
\end{equation}
The ``change time" $t^*$ denotes the time at which $x_\time$ enters the absorbing state 1,
i.e., \begin{equation} t^* = \inf\{\time > 0: x_\time = 1\} . \label{eq:tau}\end{equation}
 Of course, in the special case when $x$ is a 2-state Markov chain (i.e., $X=2$),
 the change time $t^*$ in (\ref{eq:tau})  is geometrically distributed. \\
For the multi-state case, to ensure that $t^*$ is finite, assume states $2,3,\ldots X$ are transient.
This  is equivalent to $\bar{A}$  in (\ref{eq:phmatrix}) satisfying  $\sum_{n=1}^\infty \bar{A}^{n}_{ii} < \infty$ for $i=1,\ldots,X-1$ (where $\bar{A}^{n}_{ii}$ denotes the $(i,i)$ element of the $n$-th power
of matrix $\bar{A}$).
With the  transition probabilities (\ref{eq:phmatrix}), the distribution of the change time $t^*$ is given by the PH-distribution
\begin{equation} \label{eq:nu}
 P(t^* = 0 )= \pi_0(1), \quad P(t^*= \time)  = \bar{\pi}_0^\prime \bar{A}^{\time-1} \underline{A}, \quad \time\geq 1 \end{equation}
 where $\bar{\pi}_0 = [\pi_0(2),\ldots,\pi_0(X)]^\prime$.
By  choosing  $(\pi_0,A)$ 
and state space dimension $X$,
 one can approximate any given  change-time distribution on $[0, \infty)$ by PH-distribution (\ref{eq:nu}); see 
\cite[pp.240-243]{Neu89}.  Indeed, PH-distributions form a dense subset for the set of all distributions.
\\
2. {\em Observations}: Since   states $2, 3,.\ldots, X$ are fictitious states that shape the PH-distributed change time (\ref{eq:nu}),
they are indistinguishable in terms of the observation $y$.
That is, $B_{2y} =B_{3y} = \cdots = B_{Xy}$ for all $y\in \mathbf{Y}$.
\\
3. {\em  Costs}: Associated with the quickest detection problem are the following costs. \\
{\em (i) False Alarm}:
Let $k^*$ denote the time $\tau_k$ at which  decision $u_{k}=0$ (stop and announce target state) is chosen, so that  the problem terminates.
If the decision to stop is made before the Markov chain reaches the target state 1, i.e., $k^* < 
t^*$, then a false
alarm penalty ${f}$  is paid.  So the false alarm penalty is ${f} \sum_{i\neq 1} I(x_{\tau_k}=e_i,u_k=1)$ where ${f}$ is a user defined non-negative constant.
The expected false alarm penalty based on the accumulated history is
\begin{equation}  \sum_{i \neq 1} {f} \E\{I(x_{\tau_k}=e_i,u_{k}=1)|\mathcal{F}_k\} = {f} (\mathbf{1}_X - e_1)^\prime \pi_k  I(u_k=1).\end{equation}
  Recall $\mathbf{1}_X$ denotes the $X$-dimensional vector of ones.\\
(ii) {\em Delay cost of continuing}: Suppose decision $u_{k} \in \{1,2,\ldots,L\}$ is taken at time $\tau_k$. So the next sampling
time  is $\tau_{k+1} = \tau_k + D_{u_k}$.
Then for any time $\time \in  [\tau_k, \tau_{k+1}-1]$,  the event $ \{x_{\time} = e_1, u_{k}\}$ signifies that a change
has occurred but not been announced by the decision maker. Since the decision maker can make the next decision (to stop
or continue) at $\tau_{k+1}$, the
 delay cost incurred  in the time  interval  $[\tau_k, \tau_{k+1}-1]$ is
  $d \sum_{t=\tau_k}^{\tau_{k+1}-1} I(x_{t} = e_1, u_{k} )$ 
  where   $d$ is a non-negative constant.
The expected delay cost in interval  $[\tau_k, \tau_{k+1}-1] = [\tau_k, \tau_k+D_{u_k}-1] $ is
\begin{equation}  d  \sum_{t=\tau_k}^{\tau_{k+1}-1} \E\{I(x_{t}= e_1,u_k )|\mathcal{F}_{k}\} 
= d e_1^\prime (I + A + \cdots + A^{D_{u_k}-1})^\prime \pi_k, \quad u_k \in \{1,2,\ldots,L\}. \end{equation}
(iii) {\em Measurement Sampling Cost}: Suppose decision $u_{k} \in \{1,2,\ldots,L\}$ is taken at time $\tau_k$.
As in (\ref{eq:cost}) let   $m_{u_{k}} = (m(x_{\tau_k}=e_i,u_{k}), i\in \mathbb{X})$ denote the non-negative measurement  cost  vector for choosing to take a measurement. 
For convenience, assume the measurement cost when choosing $u=0$ (stop) is zero.
Next, since in quickest detection, states $2,\ldots,X$ are fictitious states that are indistinguishable in terms of cost, choose $m(e_2,u) =\ldots = m(e_X,u)$.\\  Examples of measurement sampling costs are:\\
(a) $m(e_i,u)$ is independent of state $i$ and action $u$.  This simple choice of a constant measurement cost at each time, still
results in non-trivial global costs for the decision maker since
this   cost is incurred  each time a measurement is made -- so
choosing a decision $u$ with smaller sampling delay will result in 
 more measurements until the final decision to stop, thereby incurring a higher
total measurement cost for the global decision maker.
\\
(b)  $m(e_i,u)$ is decreasing in $u$ for $u\neq 0$. 
Choosing $m(e_i,u)$ to decrease in $u$  penalizes  choosing small sampling intervals  even more than  a constant cost.

{\bf Summary and  Kolmogorov--Shiryayev criterion}: To summarize, the costs  $C(\pi,u)$  for quickest detection with optimal sampling and PH-distributed change time are
\begin{align}
C(\pi,0) &= {f} (\mathbf{1}_X - e_1)^\prime \pi , \quad C(\pi,u) = c_u^\prime \pi + m_u^\prime \pi , \text{ for } u \in \{1,2,\ldots,L\} , \nonumber\\
\text{ where } &
c_u = d (I+A+ \cdots + A^{D_u-1}) e_1  .\label{eq:qdcosts} \end{align}

\begin{comment}
To summarize,  the quickest detection costs $\bar{C}(\pi,u)$ and Bellman's equation for the optimal strategy are (we use the notation
$\bar{C}$, etc since a coordinate transformation will be applied below)
\begin{align}
\bar{C}(\pi,0) &= {f}^\prime \pi, \quad \bar{C}(\pi,u) = de_1^\prime (I+A+ \cdots + A^{D_u-1})^\prime \pi + m_u^\prime \pi , \text{ for } u \in \{1,2,\ldots,L\} .\label{eq:qdcosts} \\
\mu^*(\pi)&= \arg\min_{u \in \{1,2,\ldots,L\}}\{ \bar{C}(\pi,0), \;\bar{C}(\pi,u)
+  \sum_{y \in \mathbf{Y}}  \bar{V}\left( T(\pi ,y,u) \right) \sigma(\pi,y,u)\} \nonumber \\
J_{\mu^*}(\pi) &= \bar{V}(\pi) = \min_{u \in \{1,2,\ldots,L\}} \{ \bar{C}(\pi,0),\; \bar{C}(\pi,u)
+ \sum_{y \in \mathbf{Y}}  \bar{V}\left( T(\pi ,y,u) \right) \sigma(\pi,y,u)\}.
  \nonumber
\end{align}
Recall, the Bayesian filter $T(\cdot)$ and normalization measure $\sigma(\cdot)$ are defined in (\ref{eq:hmm}).
\end{comment}

For  constant
measurement cost $m(x,u) = m$, $u\in \{1,2,\ldots,L\}$, 
the quickest detection optimal sampling objective
 (\ref{eq:cost}) with costs (\ref{eq:qdcosts})  can be expressed as 
 \begin{equation} J_\mu(\pi_0) =   d \E^\mu_{\pi_0}\{(k^* - t^*)^+\} + {f} \P^\mu_{\pi_0}(k^* < t^*)  +
 m \sum_{u=1}^L \sum_{k:\tau_k \leq k^*} \P^\mu_{\pi_0}(u_k = u)
\label{eq:ks}
\end{equation}
where the PH-distributed change time
 $t^*$  and $k^*$ are
defined in (\ref{eq:tau}),  (\ref{eq:kstar}).
For the special case
$\mathcal{U}=\{0 \text{ (stop)} ,D_1=1\}$, measurement cost $m_u = 0$,  geometrically
distributed $t^*$ (so $X=2$), then (\ref{eq:ks}) 
becomes the  Kolmogorov--Shiryayev
criterion for detection of disorder \cite{Shi63}.



\begin{comment}       
Before proceeding, we rewrite (\ref{eq:qdcosts}) in a form that is more amenable for analysis. Note that 
the elements of $\bar{C}(e_i,0) = f_i$ are not decreasing,  since the false alarm vector ${f}$
satisfies $f_1 = 0$ and $f_2 > 0$ (see (\ref{eq:falsev})). In our analysis below (Assumption A1 below), we will require that
the elements of the cost vector  are decreasing with respect to $i \in \mathbb{X}$. We can re-express (\ref{eq:qdcosts}) in the following
form which satisfies this property:
Define 
\begin{align}
V(\pi) &= \bar{V}(\pi) - \bar{C}(\pi,0) = \bar{V}(\pi) - {f}^\prime \pi, \nonumber \\
C(\pi,0 ) & = 0, \quad C(\pi,u) = \bar{C}(\pi,u) - {f}^\prime (I-{A^\prime}^{D_u}) \pi , \; u \in \{1,2,\ldots,L\}.  \label{eq:costdef} \end{align}
Then clearly $V(\pi)$ satisfies Bellman's dynamic programming  equation (\ref{eq:dp_alg}) and the optimal strategy $\mu^*(\pi)$ remains
unchanged. With this transformation, $C(\pi,0)$ is zero. Sufficient conditions will be given below that ensure that $C(e_i,u)$ are decreasing with $i$
for each $u \in\{1,2,\ldots,L\}$. \end{comment}


\section{Structural Results for Optimal Sampling Policy $\mu^*(\pi)$ for 2-state case} \label{sec:geom}
This section analyzes the structure of the optimal sampling strategy $\mu^*(\pi)$ (solution of Bellman's equation (\ref{eq:dp_alg})) for two-state Markov chains ($X=2$).
Recall that two-state Markov chains model geometric distributed change times in quickest detection problems.

We list the following assumptions that will be used in this section.

\begin{compactitem}
\item[{\bf (A1)}] (i) The costs $C(e_i,u)$  in (\ref{eq:cost})  are increasing with $i \in \mathbb{X}$ for each $u \in \mathcal{U}$.\\
(ii) The target state $e_1$ belongs to the stopping set $\mathcal{S}$ defined in (\ref{eq:stopset}).
\item[{\bf (A2)}] The transition matrix $A$ is totally positive of order 2 (TP2). That is, all second order minors are non-negative.
\item[{\bf (A3)}] The observation matrix $B$ is TP2.
\item[{\bf (A4)}] $C(e_i,u)$ is submodular for $u\in\{1,2,\ldots,L\}$, that is $C(e_i,u+1)-C(e_i,u)$ is decreasing\footnote{Throughout this paper, we use the term ``decreasing" in the weak sense. That is ``decreasing" means
non-increasing. Similarly, the term ``increasing" means non-decreasing.}  in $i \in \mathbb{X}$.
\end{compactitem}

Consider the following assumption  where  $A^{D_u}\vert_{ij}$ denotes the $(i,j)$ element of matrix $A^{D_u}$:

\begin{itemize}
\item[{\bf (A5-(i))}]  For each $q\in \mathbb{X}$,  $\sum_{j\geq q} A^{D_u}\vert_{i j}$ is submodular. That is,
$\sum_{j\geq q} A^{D_{u+1}}\vert_{ij} - A^{D_u}\vert_{ij}$  is decreasing in $i \in \mathbb{X}$ for $u=1,2,\ldots,L-1$.
\item[{\bf (A5-(ii))}] $A^{D_u}\vert_{22}$ and $A^{D_u}\vert_{12}$ is decreasing in $u \in \{1,2,\ldots,L\}$.
\end{itemize}



These assumptions are discussed below in Sec.\ref{sec:discussion} and hold for quickest detection problems.


\subsection{Optimality of Threshold Policy for Sequential Optimal Sampling} \label{sec:2state}
Note that for a 2-state Markov chain ($X=2$), the belief state space $\Pi(X)$ is the one dimensional simplex $\pi(1)+\pi(2) = 1$. So it suffices to represent $\pi$ by its first element
 $\pi(1)$. 



\begin{framed}
\begin{theorem} \label{thm:main1}
Consider the optimal sampling  problem of Sec.\ref{sec:qdbasic} with state dimension $X=2$ and action space $\mathcal{U}$ (\ref{eq:actionstrategya}). Then
the optimal strategy $\mu^*(\pi)$ in (\ref{eq:dp_alg}) has the following structure:
\\
(i) The optimal stopping set $\mathcal{S}$ (\ref{eq:stopset}) is a convex subset of $\Pi(X)$. Therefore under (A0), the stopping set is the interval
 $\mathcal{S} = (\pi_1^*,1]$ where
the threshold $\pi^* \in [0,1]$.\\
(ii) Under
assumptions (A1-A5),  the optimal sampling strategy  $\mu^*(\pi)$ in (\ref{eq:dp_alg}) is  decreasing with $\pi(1)$. Thus, there exist up to $L$ thresholds denoted $\pi_1^*, \ldots, \pi_L^*$ with
 $0 \leq \pi_L^* \leq \pi_{L-1}^* \leq \cdots \leq \pi_1^* \leq 1 $ such that the optimal strategy satisfies
 \begin{equation} \label{eq:thres}
 \mu^*(\pi) = \begin{cases}  L \text{ (sample after  $D_L$ time points) } & \text{ if } 0 \leq \pi(1) < \pi_L^* \\
 					{L-1} \text{ (sample after  $D_{L-1}$ time points) } & \text{ if }  \pi_L^* \leq \pi(1) < \pi_{L-1}^* \\
					\vdots & \vdots \\
					 1 \text{ (sample after  $D_{1}$ time points) } & \text{ if } \pi_{2}^* \leq \pi(1) < \pi_1^*  \\
					 0 \text{ (announce change )} & \text{ if } \pi_1^* \leq \pi(1) \leq 1 \end{cases}
 \end{equation}
 where the sampling delays are ordered as $D_1 < D_2 < \ldots < D_L$.
\end{theorem}
\end{framed}

The proof of Theorem \ref{thm:main1} is in Appendix \ref{app:main1}.
As an  example, consider   quickest detection with optimal sampling for geometric distributed change time.
 From (\ref{eq:phmatrix}),   the transition matrix is 
$ A = \begin{bmatrix} 1 & 0 \\ 1-A_{22} & A_{22} \end{bmatrix}$ and expected change time is $\E\{t^*\} = \frac{1}{1-A_{22}}$
where $t^*$ is defined in (\ref{eq:tau}).

\begin{framed}
\begin{theorem}\label{cor:qd}
Consider the  quickest detection problem with optimal sampling  and geometric-distributed change time formulated in Sec.\ref{sec:exqd} with costs
defined in (\ref{eq:qdcosts}).
 Assume the measurement cost $m(x,u)$ satisfies (A1) and (A4), e.g., the measurement cost is a constant.
Then if (A3)  holds, 
Theorem \ref{thm:main1} holds. So the optimal sampling strategy (\ref{eq:thres}) makes measurements  less 
frequently when away from the target state and more  frequently when
closer to the target state.   (Note, (A1)(ii),  (A2), (A5) hold automatically and no assumptions are required on the delay or stopping costs in
(\ref{eq:qdcosts})).
\end{theorem}
\end{framed}


There are two main conclusions regarding Theorem \ref{cor:qd}. First, for constant measurement cost, Theorem \ref{cor:qd} holds
without any assumptions for Gaussians, exponentials, and several other 
 classes
 of observation distributions that satisfy (A3).
Second, the optimal strategy 
 $\mu^*(\pi)$ is monotone  in posterior $\pi(1)$ and therefore has a finite dimensional characterization. To determine the optimal strategy, one only
 needs to determine (estimate) the values of the $L$ thresholds 
 $\pi_1^*, \ldots, \pi_L^*$. These can be estimated via a simulation-based stochastic optimization algorithm. We will  give bounds for these threshold values
 in Sec.\ref{sec:main}. Fig.\ref{fig:thm1} illustrates such a monotone policy.



A short word on the proof  presented in Appendix \ref{app:main1}. It  involves
 analyzing the structure of Bellman's equation (\ref{eq:dp_alg}). It will  be shown that
 $Q(\pi,u)$  in   (\ref{eq:dp_alg}) is a submodular function (defined in Appendix \ref{app:main1}) on  the partially ordered set $[\Pi(X),\geq_r]$ 
 which constitutes a lattice. Here $\geq_r$ denotes the monotone likelihood
 ratio stochastic order defined in Sec.\ref{sec:filter}.
 For $X=2$, $\Pi(X)$ is  the unit interval [0,1]  and in this case $[\Pi(X),\geq_r]$ is a chain (totally ordered set) and $\geq_r$ is equivalent to first order 
 stochastic dominance. For $X\geq 2$ considered in the next section, a similar idea is used to bound the optimal policy on $[\Pi(X),\geq_r]$.

{\em Remark: Interpretation of \cite{BV12}}.  We comment here briefly on the recent paper \cite{BV12} which considers quickest  detection
with measurement control where
at each time the decision is made  whether to take a measurement
or not. This
 can be formulated as our optimal sampling problem by considering the action
space $\mathcal{U} =\{0 \text{ (announce change)} ,\D_1,\D_2,\ldots,\D_L\}$ with sampling interval $D_i = i$ and $L$ chosen sufficiently large.
In \cite{BV12}, a different action space is chosen, namely $\{ 0 \text{ (announce change)}, m \text{ (take measurement)}, \bar{m} \text{ (no measurement)} \}$.
With this action space, \cite{BV12} shows that the optimal strategy is not necessarily monotone in the posterior. $\pi$.  However, with the
action space $\mathcal{U}$ defined above, Theorem \ref{cor:qd} shows that the optimal strategy indeed is monotone.

We can interpret the non-monotone optimal strategy in \cite{BV12} as follows.  
Our action 1 (sample next point) corresponds to action $m$ in \cite{BV12}, action 2 (sample after 2 points) corresponds to $(\bar{m},m)$, action 3 (sample after 3 points) corresponds to $(\bar{m},\bar{m},m)$, etc.
Reading off the monotone optimal strategy $\mu^*(\pi) \in 
\{3, 2,1\}$ versus $\pi$ using the action
space of \cite{BV12}  yields strategy $\{\bar{m},\bar{m},m, \bar{m},m, m\}$ which
is non-monotone, due to presence of the action $\bar{m}$ sandwiched between two $m$'s.\footnote{\cite{BV12} also contains a very nice performance analysis of sub--optimal and nearly optimal strategies. This analysis may be applicable to our setup due to similarity of the models.}



\subsection{Discussion of Assumptions A1-A5}\label{sec:discussion}  To illustrate the assumptions of Theorem \ref{thm:main1}, we will now prove Theorem \ref{cor:qd}
by showing that assumptions  that (A1-A5)  hold.
 Recall  from (\ref{eq:phmatrix}) that for quickest detection with geometric change time, the transition matrix is 
\begin{equation} A = \begin{bmatrix} 1 & 0 \\ 1-A_{22} & A_{22} \end{bmatrix}.  \text{ So } \;
A^{D_u} = \begin{bmatrix} 1 & 0 \\ 1-A^{D_u}_{22} & A^{D_u}_{22} \end{bmatrix} . \label{eq:tpg}\end{equation}
\subsubsection{Assumption (A1)(i)} This
requires the elements of the cost vector to be increasing. However, in quickest detection, the instantaneous cost $c(e_i,u)$ for $u\geq 1$  defined in (\ref{eq:qdcosts}) is {\em decreasing} in $i$ if the measurement cost $m$
 is a constant. 
But all is not lost.
Remarkably, a  clever transformation can be applied to make a transformed version  of the cost  {\em increase} with $i$ and yet 
ensure (A4) holds and keep the optimal strategy unchanged! This transformation is crucial for proving Theorem~\ref{cor:qd}, particularly for constant measurement cost. (Assuming a measurement cost increasing in the state $i$ makes
the proof  easier but may be unrealistic in applications).
We define this transformation via the following theorem - it exploits the special structure of the quickest detection problem.

\begin{theorem} \label{lem:transform}
Consider the quickest time detection problem with costs defined in  (\ref{eq:qdcosts}).
Assume the sampling cost $m(e_i,u)$ is a constant. Define the transformed costs $\underline{C}(\pi,u)$  as follows:
\begin{align}  \underline{C}(\pi,0) &= C(\pi,0) - \alpha C(\pi,L),  \nonumber \\
\underline{C}(\pi,u) &=  C(\pi,u) - \alpha C(\pi,L) + \alpha \sum_y C(T(\pi,y,u),L) \sigma(\pi,y,u), \quad u \in \{1,2,\ldots,L\} 
\label{eq:transform}
\end{align}
for any constant $\alpha \in \mathbb{R}$.
Then:\\
(i) Bellman's equation (\ref{eq:dp_alg}) applied to optimize the    global objective (\ref{eq:cost}) with transformed costs $\underline{C}(\pi,u)$
yields the same optimal strategy  $\mu^*(\pi)$ as the global objective with  original costs $C(\pi,u)$.
\\
(ii) Choosing $\alpha = 1/(1-A_{22}^{D_u})$  implies $\underline{C}(e_i,u)$ satisfies (A1) and (A4).
 \qed
\end{theorem}

 Theorem \ref{lem:transform} is proved in Appendix \ref{app:transform}.
It 
 asserts that the transformed costs $\underline{C}(e_i,u)$  satisfies (A1) and (A4) even for constant measurement cost. 
Therefore Theorem \ref{thm:main1} holds and the optimal strategy for the transformed costs is monotone in the posterior distribution.
Note that  Theorem \ref{lem:transform} also says that  the optimal
strategy $\mu^*(\pi)$ is unchanged by this transformation. Thus  Theorem \ref{thm:main1}  holds for the original quickest detection costs,
thereby proving Theorem \ref{cor:qd}.

 {\em Assumption (A1)(ii)} is natural for the stopping problem to be well defined. It says that if it was known with certainty that the target state $e_1$
has been reached, then it is optimal to  stop. For quickest time detection it holds trivially since $C(e_1,0) \leq  C(\pi,u)$ for  $u\in \{1,\ldots,L\}, \pi \in \Pi(X)$.



\subsubsection{Assumption
(A2)}  From  the structure of transition matrix $A$ in (\ref{eq:tpg}),  clearly (A2) holds automatically for the quickest detection problem.  For numerous examples of TP2 transition matrices, see \cite{KR80}. Also,  $A$ does not need to have an
absorbing state for Theorem \ref{thm:main1} to hold.

\subsubsection{Assumption (A3)} Numerous continuous and discrete  noise distributions satisfy the TP2 property, see \cite{KR80}. Examples include Gaussians, Exponential, Binomial, Poisson, etc.
Examples of discrete observation distribution  satisfying (A3) include
binary erasure channels
-- see   Sec.\ref{sec:numerical}.  A binary symmetric channel with error probability less than 0.5 also satisfies (A3).

 
\subsubsection{Assumption (A4)} In general Theorem \ref{thm:main1} requires the costs $C(e_i,u)$ to be submodular. 
However, for the special case of quickest detection with optimal sampling, from Theorem \ref{lem:transform} shows that only
the measurement cost $m(e_i,u)$ needs to be submodular, i.e., $m(e_i,u+1)-m(e_i,u)$ is decreasing in $i$.  This holds trivially  if the measurement cost
is independent of the state.

\subsubsection{Assumption
(A5)} This is a submodularity condition on the transition matrix.  Since from (\ref{eq:tpg}) $A^{D_u}\vert_{21} = 0$ and $A^{D_u}\vert_{22} =  A_{22}^{D_u}$, clearly (A5) holds automatically for the quickest detection problem with optimal sampling.

\section{Myopic  Bounds to Optimal  Strategy for multi-state Markov Chain} \label{sec:main}
This section considers the optimal sampling problem for multi-state Markov chains ($X\geq 2$).
Recall that multi-state Markov chains can model PH-distributed change times (\ref{eq:phmatrix}) in quickest detection problems.
 Theorems \ref{thm:myopic} and \ref{cor:qd2} are the main results of this section.  They characterize the structure of
optimal strategy $\mu^*(\pi)$ which is the solution of Bellman's equation (\ref{eq:dp_alg}).


 Define the following ordering of two arbitrary transition matrices $A^{(1)}$ and $A^{(2)}$: 
\begin{equation} A^{(1)}\succeq A^{(2)} \text{ if } A^{(1)}_{ij} A^{(2)}_{m,j+1} \leq A^{(2)}_{ij} A^{(1)}_{m,j+1}, \quad i,j+1,m \in \mathbb{X}. \label{eq:mor}\end{equation}

The following are the main assumptions used in this section:
\begin{compactitem}
\item[{\bf (A6)}] The transition matrix satisfies $A \succeq A^{2}$ where the ordering $\succeq$ is defined in (\ref{eq:mor}).
\item[{\bf (A7)}] There exist a positive constant $\alpha$ satisfying \\ (i) $\alpha \geq f/(d(1-A_{21}))$ \\
(ii) $\sum_{l=1}^{D_u-1} A^l|_{i1} + \alpha (A_{i1} - A^{D_u+1}|_{i1}) $ decreasing in $i=2,\ldots,X$.
\end{compactitem}

(A6) and (A7) are discussed at the end of this section.
(A6) and (A7) hold trivially for the two state Markov  chain case ($X=2$) with absorbing state when $A$ is of the form (\ref{eq:tpg}). Examples for $X\geq 3$ are given in Sec.\ref{sec:numerical}.


\subsection{Myopic Lower Bound to Optimal Policy}
 For  multi-state Markov chain observed in noise, determining sufficient conditions for the
optimal strategy to have a  monotone structure
 is an open problem.  
In this section we show that the optimal sampling strategy $\mu^*(\pi)$ is lower bounded by a  myopic strategy.
Define the  myopic strategy  ${\underline{\mu}}(\pi)$  and myopic stopping set $\underline{\mathcal{S}} $ by
\begin{align} {\underline{\mu}}(\pi) &= \arg\min_{u \in \mathcal{U}} C(\pi,u)    \nonumber\\
 \label{eq:ustop}
\underline{\mathcal{S}} =   \{\pi \in \Pi(X) : \underline{\mu}^*(\pi) = 0\} &=  \{\pi \in \Pi(X):  C(\pi,0) <  C(\pi,u), \; u \in \{1,2,\ldots,L\} \} \end{align}
So $\underline{\mathcal{S}}$ is the set of belief states for which  the myopic strategy declares stop.
 
The following is the main result of this section. The proof is in Appendix \ref{app:myopic}.

 \begin{framed}
\begin{theorem} \label{thm:myopic}
Consider the sequential sampling  problem of Sec.\ref{sec:qdbasic} with optimal strategy specified by (\ref{eq:dp_alg}). Then
\begin{enumerate}
\item The stopping set $\mathcal{S}$ defined in (\ref{eq:stopset}) is a convex subset of the belief state space $\Pi(X)$.
\item $\underline{\mathcal{S}} \subset \mathcal{S}$ where $\underline{\mathcal{S}}$ is the myopic stopping set defined in (\ref{eq:ustop}).
\item Under (A1), (A2), (A3), (A6),
the myopic strategy 
 ${\underline{\mu}}(\pi)$ defined in (\ref{eq:ustop}) forms  a lower   bound for the optimal
strategy $\mu^*(\pi)$, i.e.,  $\mu^*(\pi) \geq {\underline{\mu}}(\pi)$ for
all $\pi \in \Pi(X) - \mathcal{S}$. 
\item If (A4) holds, then the myopic strategy is ${\underline{\mu}}(\pi)$ is increasing with $\pi$ (with respect
to the monotone likelihood ratio (MLR) stochastic order to be defined in Sec.\ref{sec:filter}). 
\end{enumerate} 
\end{theorem} \end{framed}

The above theorem says  that the myopic strategy  ${\underline{\mu}}(\pi)$  comprising of increasing step functions
lower bounds the optimal strategy $\mu^*(\pi)$.
The myopic strategy specified by (\ref{eq:ustop}) is computed trivially on the 
 simplex $\Pi(X)$.
Therefore, the above theorem gives a useful lower bound ${\underline{\mu}}(\pi)$ for the optimal strategy $\mu^*(\pi)$ (which
is intractable to compute). 
  Also since ${\underline{\mu}}(\pi)$ is sub-optimal, it incurs a higher cost compared to the optimal strategy. This cost associated
  with ${\underline{\mu}}(\pi)$ can be evaluated by simulation and forms an upper bound to the optimal achievable cost.


\subsection{Quickest Detection with Optimal Sampling for PH-Distributed Change Time}
We now use 
Theorem \ref{thm:myopic}  to construct a myopic strategy  that upper bounds  the optimal  strategy for  quickest detection with sampling for  PH-distributed change time. 
 However, (A1) does not hold for the quickest detection costs $C(\pi,u)$ in (\ref{eq:qdcosts})
To proceed, it is convenient to define the following transformed cost $\bar{C}(\pi,u)$ and myopic strategy  $\bar{\mu}(\pi) $:
\begin{align} \label{eq:bmu}
\bar{C}(\pi,0) &= C(\pi,0) + \alpha  d e_1^\prime A ^\prime \pi, \\
\bar{C}(\pi,u) &= C(\pi,u) + \alpha  d e_1^\prime A ^\prime \pi -  \alpha  d e_1^\prime {A^\prime}^{D_u+1}  \pi,  \quad u \in \{1,2,\ldots,L\}, \nonumber\\
\quad  \bar{\mu}(\pi) &= \arg\min_{u \in \{1,2,\ldots,L\}} \bar{C}(\pi,u) . \nonumber \end{align}



It will be shown in the proof of the theorem below, that the optimal strategy for global objective (\ref{eq:cost})
with these transformed costs $\bar{C}(\pi,u)$ remains unchanged and is still $\mu^*(\pi)$.


 

The main result regarding quickest detection with optimal sampling for PH-distributed change times is as follows. The proof is in Appendix \ref{app:qd2}.
\begin{framed}
\begin{theorem} 
\label{cor:qd2}
Consider the quickest detection  optimal sampling  problem for PH-distributed change time ($X\geq 2$) defined in Sec.\ref{sec:exqd} with
costs in (\ref{eq:qdcosts}) and  transformed costs (\ref{eq:bmu}). Then
\begin{compactenum}
\item The optimal stopping set $\mathcal{S}$  (\ref{eq:stopset}) is a convex subset of the belief state space $\Pi(X)$ and contains $e_1$. 
\item   The optimal stopping set is lower  bounded
by the  myopic stopping set $\underline{\mathcal{S}}$ in (\ref{eq:ustop}), i.e., 
$\underline{\mathcal{S}}  \subset \mathcal{S}$.
\item Under (A2), (A3), (A6), (A7),  for $\pi \in \Pi(X) - \underline{\mathcal{S}}$, the myopic strategy $\bar{\mu}(\pi) $ in (\ref{eq:bmu})  upper bounds the optimal strategy, i.e., $\bar{\mu}(\pi) \geq \mu^*(\pi) \text{  for all } \pi \in \Pi(X)- \underline{\mathcal{S}}$. Moreover, $\bar{\mu}(\pi) $ is increasing  in $\pi$ with respect to the MLR order.
\item  For the case of geometrically distributed change time ($X=2$), 
 (A2) and (A6) hold automatically. So if (A3) holds and $\alpha$ is chosen according to (A7)(i), 
 then  $\bar{\mu}(\pi) \geq \mu^*(\pi)$ for all $\pi \in \Pi(X)$. Also
  $\bar{\mu}(\pi)$
 is decreasing in $\pi(1)$. \end{compactenum}

 \end{theorem}
\end{framed}



{\em Discussion}: Theorem \ref{cor:qd2} gives a lot of analytical mileage in terms of bounding the optimal strategy.
 Statements (1)  characterizes  the convexity of the stopping set and  Statement (2) lower  bounds 
$\mathcal{S}$. 
Statement (3)  asserts that the optimal sampling strategy $\mu^*$ can be upper bounded for PH-distributed change times by the myopic
strategy $\bar{\mu}$.

 Statement (4) shows that for geometrically distributed change times,
the bounds on $\mu^*$ and $\mathcal{S}$ apply without requiring any assumptions apart from that on the observation distribution (A3).
In particular, Statement (4) together with Theorem \ref{cor:qd}  say that the optimal strategy $\mu^*(\pi)$ is monotone in $\pi(1)$, and upper bounds
for the threshold values $\pi_1^*, \pi_2^*,\ldots, \pi_L^*$ can be constructed using the myopic  strategy $\bar{\mu}(\pi)$. Therefore these upper bounds can be used to initialize
a stochastic optimization algorithm to estimate the thresholds of the optimal monotone policy.

{\em Discussion of Assumptions (A6) and (A7)}:
(A6) is a  sufficient to preserve monotone likelihood ratio (MLR) dominance of the belief state with a one-step predictor.
MLR stochastic order $\geq_r$ is defined
in Sec.\ref{sec:filter}. (A6) ensures that if two belief states satisfy $\pi_1\geq_r \pi_2$, then the one-step ahead
Bayesian predictor satisfies $A^\prime \pi_1 \geq_r A^\prime \pi_2$. Theorem \ref{thm:filter} in Sec.\ref{sec:filter} analyzes this
and other stochastic
dominance properties of Bayesian filters and predictors that are crucial to prove the results of this paper. 


(A7) is sufficient  for the transformed cost $\bar{C}(\pi,u)$ defined in (\ref{eq:bmu}) to satisfy the following:
$-\bar{C}(\pi,u)$ satisfies (A1) and $\bar{C}(\pi,u)$ to satisfies (A4). The fact that $\bar{C}(\pi,u)$ is decreasing
(since its negative satisfies (A1)), gives an upper bound by a proof completely analogous to Theorem~\ref{thm:myopic}. 

\section{Performance and Sensitivity of Optimal Strategy}
In previous sections, we have presented structural results on monotone  optimal {\em strategies}. In comparison, this section focuses on
{\em achievable costs} attained by the optimal strategy.
This section presents  two results. First, we give bounds on the achievable performance of the optimal strategies by the decision maker.
This is done by introducing a partial ordering of the transition and observation probabilities -- the larger these parameters with respect to this order, the larger the 
optimal cost incurred. Thus we can compare models and bound the achievable performance of a computationally intractable problem.
Second, we give explicit bounds on the sensitivity of the total sampling cost with respect
to sampling model -- this bound can be expressed in terms of the Kullback-Leibler divergence. Such a robustness result
is useful since even if a model violates
the assumptions of the previous section, as long as the model is sufficiently close to a model that satisfies the conditions, then the optimal
strategy is close to a monotone strategy. 


\subsection{How does total cost of the optimal sampling strategy depend on state dynamics?} \label{sec:order}

Consider the optimal sampling problem formulated in Sec.\ref{sec:qdbasic}. 
How does the  optimal expected  cost $J_{\mu^*}$ defined in (\ref{eq:mustar}) vary
  with
 transition matrix $A$ and observation matrix $B$? In particular, is it possible to devise an ordering for transition
 matrices and observation distributions
 such that the larger they are, the smaller the optimal sampling cost? Such a result would allow us to compare the optimal
 performance of different sampling models, even though computing these is intractable. Moreover, characterizing how the optimal
 achievable cost varies with transition matrix and observation distribution is useful.
  Recall in quickest detection the transition matrix specifies the change time distribution.
 In sensor scheduling applications the transition matrix specifies the mobility of the state. The observation matrix specifies
 the noise distribution.
 
 Consider two distinct models $\theta= (A,B)$ and $\bar{\model} = (\bar{A},\bar{B})$ of the optimal sampling problem where
$A,\bar{A}$ are transition matrices and $B, \bar{B}$ are observation matrices.
Let $\mu^*(\theta)$ and $\mu^*({\bar{\model}})$ denote, respectively, the optimal strategies for these two different models.
 Let $J_{\mu^*(\theta)}(\pi;\theta) =  V(\pi;\theta)$ and 
$J_{\mu^*(\bar{\model})}(\pi;\bar{\model}) =V(\pi;\bar{\model})$ denote the   optimal value functions in (\ref{eq:dp_alg}) corresponding to applying the respective optimal strategies.
Recall  also that the costs in (\ref{eq:cost}) depend on the transition matrix $A$. So we will use the notation $C(\pi,u;\theta)$ 
and $C(\pi,u;\bar{\model})$ to make
the dependence of the cost on the transition matrix explicit.

Introduce the following {\em reverse Blackwell ordering} \cite{Rie91} of observation distributions. Let $B$ and $\bar{B}$ denote
two observation distributions defined as in (\ref{eq:obs}). Then $\bar{B}$ reverse Blackwell dominates $B$ denoted
as 
\begin{equation} \bar{B} \succeq_B  B \text{ if }  \bar{B} = B R  \label{eq:blackwell}\end{equation}
where $R= (R_{lm})$ is a stochastic kernel, i.e., $\sum_mR_{lm} = 1$.  This means that $B$ yields more accurate measurements
of the underlying state than $\bar{B}$.


{\em The question we pose is:  How does the optimal cost
$J_{\mu^*(\theta)}(\pi;\theta)$ vary with transition matrix $A$ and observation distribution $B$?} For example, in the quickest  detection optimal sampling
problem, do certain phase-type distributions result in larger total optimal cost compared to other phase-type
distributions? 


\begin{framed}
\begin{theorem} \label{thm:tmove}
 Consider two optimal sampling problems with models $\theta=(A,B)$ and $\bar{\model}=(\bar{A},\bar{B})$, respectively. Assume ${A} \succeq \bar{A}$
 with respect to ordering (\ref{eq:mor}),
  $B \succeq_B \bar{B}$ with respect to ordering (\ref{eq:blackwell}), and
  (A1), (A2), (A3)  hold. Then the expected total costs incurred by the optimal sampling
  strategies  satisfy
 $J_{\mu^*(\theta)}(\pi;\theta) \geq J_{\mu^*(\bar{\model})}(\pi;\bar{\model})$.
That is, the larger the transition matrix and observation matrix  (with respect to the partial  ordering (\ref{eq:mor}) and (\ref{eq:blackwell})),
the lower the  expected total  cost of the optimal sampling strategy.
 \end{theorem} \end{framed}



The proof is in Appendix \ref{app:tmove}.
Computing the optimal strategies of a POMDP and therefore optimal costs
 is  intractable. Yet, the above
theorem allows us to compare these optimal  costs for different transition and observation matrices.  The implication for quickest  detection with optimal sampling  is that
we can compare the optimal cost for different PH-distributed change times and noise distributions. The implication for sensor scheduling is that we can 
apriori say that certain state dynamics incur a larger overall cost compared to other dynamics and noise distributions.

As a trivial consequence of the theorem, the optimal cost incurred with perfect measurements is always smaller than
that with noisy measurements. Since the optimal sampling problem with perfect measurements is a full observed MDP (or equivalently,
infinite signal to noise ratio), the 
corresponding optimal cost forms a easily computable lower bound to the achievable cost.



\subsubsection*{Examples} Here are examples of transition matrices $A ,\bar{A}$ that satisfy (A3) and $A \succeq \bar{A}$. \\
{Example 1}. Geometric distributed change time: $A = \begin{bmatrix} 1 & 0 \\ 1- A_{22} & A_{22} \end{bmatrix}$,
$\bar{A} = \begin{bmatrix} 1 & 0 \\ 1- \bar{A}_{22} & \bar{A}_{22} \end{bmatrix}$  where $  A_{22} < \bar{A}_{22} $.\\
{Example 2. } PH-distributed change time:  $A = \begin{bmatrix} 
1 & 0 & 0 \\ 0.5 & 0.3 & 0.2 \\
0.3 & 0.4 & 0.3 \end{bmatrix}$, $  \bar{A} = \begin{bmatrix}
1 & 0 & 0 \\ 0.9 & 0.1 & 0 \\ 0.8 & 0.2 & 0 \end{bmatrix} $.\\
{Example 3. } Markov chain without absorbing state: $ A = \begin{bmatrix} 0.2  & 0.8 \\ 0.1 & 0.9 \end{bmatrix} , \quad \bar{A} =  \begin{bmatrix}  0.8 & 0.2 \\ 0.7 & 0.3 \end{bmatrix}$
 
  Theorem \ref{thm:tmove} applies to all these examples implying that the total cost of the optimal policy with $A$ is larger than that with
  $\bar{A}$.




\subsection{Sensitivity to Mis-specified Model}
How sensitive is the total sampling cost to the choice of sampling strategy?
Given two distinct models $\theta= (A,B)$ and $\bar{\model} = (\bar{A},\bar{B})$ of the optimal sampling problem,
Theorem  \ref{thm:tmove} above compared their optimal costs -- it showed that  $\theta \succeq \bar{\model} \implies J_{\mu^*(\theta)}(\pi;\theta) \leq J_{\mu^*(\bar{\model})}(\pi;\bar{\model})$,  where
$\mu^*(\theta), \mu^*(\bar{\model})$ denote the optimal sampling strategies for models $\theta,\bar{\model}$, respectively.
(where  the ordering $\succeq$ is specified in Sec.\ref{sec:order}). In this section, we establish the following type of sensitivity result 
(where the norm $\|\cdot\|$ is defined in Theorem \ref{thm:sens} below):
\begin{equation}
\sup_{\pi\in \Pi(X)} |J_{\mu^*(\theta)}(\pi;\theta) - J_{\mu^*(\theta)}(\pi;\bar{\model})| \leq
K\|\theta - \bar{\model}\|  \label{eq:sens0}\end{equation}
and,
we will give an explicit representation for the positive constant $K$ in Theorem \ref{thm:sens} below.

 Note the key difference between (\ref{eq:sens0}) 
and  Theorem \ref{thm:tmove}.
In (\ref{eq:sens0}), we are applying the optimal strategy $\mu^*(\theta)$ for model   $\theta$ 
to the decision problem with a different model  $\bar{\model}$.
Of course, this results in sub-optimal behavior. But we will show that if the ``distance'' between the two models
$\theta,\bar{\model}$  is small, then the sub-optimality is small --  that is,  the increase in total cost by using
the strategy $\mu^*(\theta)$ to the decision problem with model $\bar{\model}$ is small. 

Define 
\begin{equation} y^*_{\theta,\bar{\model}} = \inf\{y:   (C_{{\bar{u}}} - C_0)^\prime T(e_X,y,u;\theta)  \leq 0 \text{ and }
(C_{{\bar{u}}} - C_0)^\prime T(e_X,y,u;\bar{\model})  \leq 0
\;\forall u,\bar{u} \in \{1,2,\ldots,L\} \} \label{eq:ystar}\end{equation}
The set depicted in (\ref{eq:ystar}) represents a subset the observation
space $\mathbf{Y}$  for
which the optimal decision is to stop. 
We assume that 
\begin{itemize}
\item[(A7)]  $P(y \leq y^*_{\theta,\bar{\model}}) > 0 $. 
\end{itemize}
Assumption  (A7) holds  trivially if the observation distribution $B_{xy}$ (defined in (\ref{eq:obs})) is absolutely continuous with respect to Lebesgue measure on $\mathbb{R}$,
 i.e., if the density  has support on $\mathbb{R}$ such as Gaussian noise. (A7) is relevant
 for cases when the observation space is finite or a subset of $\mathbb{R}$.


\begin{framed}
\begin{theorem} \label{thm:sens}
Consider two optimal sampling problems  with models $\theta= (A,B)$ and $\bar{\model}= (\bar{A},\bar{B})$, respectively.
 Let $J_{\mu^*(\theta)}(\pi;\theta)$ and
$J_{\mu^*(\theta)}(\pi;\bar{\model})$ denote the total costs (\ref{eq:cost}) incurred by these models
 when using strategy $\mu^*(\theta)$. Assume $\theta$ and $\bar{\model}$ satisfy  (A2), (A3), (A4), (A7).
 Then the difference in the total costs is upper-bounded as:
\begin{align} \label{eq:sens}
& \sup_{\pi \in \Pi(X)}  |J_{{\mu^*(\theta)}}(\pi;\theta) - J_{{\mu^*(\theta)}}(\pi;\bar{\model})|  \leq \max_i C(e_i,0)   \frac{\|\theta-\bar{\model}\|}{1-\rho_{\theta,\bar{\model}}} \\
\text{ where } & 
\rho_{\theta,\bar{\model}}  = \max_u \sum_{y \geq y^*_{\theta,\bar{\model}}} \sigma(e_X,y,u;\theta) 
, \quad  
\|\theta-\bar{\model}\| =  \max_{i,u} \sum_{j,y} \left| B_{jy}A^{D_u}\vert_{ij}-\bar{B}_{jy} {\bar{A}}^{D_u}\vert_{ij} \right|. \nonumber
 \end{align}
\end{theorem} \end{framed}
\begin{framed}
 \begin{corollary} \label{cor:kl}
 Consider two optimal sampling problems  with models $\theta$ and $\bar{\model}$, respectively.
 Assume they  have identical transition matrices, but different observation distributions denoted $B,\bar{B}$ (where $B$ is defined in (\ref{eq:obs}).
 Then bound (\ref{eq:sens}) holds with
 \begin{align}
 \|\theta-\bar{\model}\| &=   \sqrt{2 } \max_{i,u} \sum_{j}  A^{D_u}\vert_{ij } \,  \left[ D(B_j \| \bar{B}_j)\right]^{1/2} \nonumber \\
 \text{where } 
 D(B_j \| \bar{B}_j) &= \sum_y B_{jy} \ln (B_{jy}/\bar{B}_{jy}) \text{ (Kullback-Leibler Divergence).} \label{eq:kl}
 \end{align}
 In particular, if the observation distributions are   Gaussians with variance $\sigma^2$, $\bar{\sigma}^2$, respectively, then
 (\ref{eq:sens}) holds with
$$ \|\theta-\bar{\model}\|  = \left(\frac{\sigma}{\bar{\sigma}} - \ln \frac{\sigma}{\bar{\sigma}}  - 1\right)^{1/2} $$
\end{corollary} \end{framed}

 The proof of Theorem \ref{thm:sens} and Corollary \ref{cor:kl} are in Appendix \ref{app:sens}.  Corollary \ref{cor:kl}  follows from Theorem \ref{thm:sens} via elementary use of the Pinsker inequality
 that bounds the total variation norm by the Kullback-Leibler Divergence.
Note that  the bound in (\ref{eq:sens}) and (\ref{eq:kl}) is tight in the sense that $\|\theta - \bar{\model}\| = 0$ 
 implies that the performance degradation is zero.  The proof is  complicated by the fact
 that  there is no discount factor\footnote{Instead of (\ref{eq:cost}), if the cost was $ J_\mu(\pi_0) = \E^\mu_{\pi_0}\left\{\sum_{k=1}^{k^*-1}  \rho^k C(\pi_{k},u_{k}) 
+ \rho^{k^*} C(\pi_{{{k^*}}}, u_{{k^*}}=0)
 \right\}  $, where the  user defined discount factor $\rho \in [0,1)$, then establishing a bound such as (\ref{eq:sens}) is  straightforward. An artificial discount factor $\rho$ is un-natural in our problem and un-necessary as shown in Theorem \ref{thm:sens} since the problem terminates in finite time with probability one and hence has an implicit discount factor denoted as $\rho_{\theta,\bar{\model}}$.}
  in the cost
 (\ref{eq:cost}). However, because the sampling problem terminates with probability one in finite time, it has an implicit
 discount factor -- this is typical in  stochastic shortest path problems that terminate in finite time \cite{Ber00b}. 
 Assumption (A7) implies that $\rho_{\theta,\bar{\model}} < 1$.
 The term $1-\rho_{\theta,\bar{\model}}$ can be interpreted as a lower bound to the 
 probability of stopping at any given time. Since this is non-zero,
the term $\rho_{\theta,\bar{\model}}$ in (\ref{eq:sens}) serves as this implicit discount factor.
  


 The above result is more than an intellectual curiosity. For optimal sampling problems where
 the  transition matrix or observation distribution do not satisfy 
assumptions  (A5), (A6) or (A7) but are $\epsilon$ close  to satisfying these conditions, the above result  ensures that a monotone strategy
yields near optimal behavior. 
with explicit bound on the performance given by (\ref{eq:sens}) and (\ref{eq:kl}).


\begin{comment}
\subsection{Optimality of Threshold Policies in High SNR}
For $X=2$, Theorem \ref{thm:main1} showed that the optimal sampling strategy was a threshold. However, 
 for $X>2$, we only showed in Theorem \ref{thm:myopic} that the optimal strategy is lower bounded by a threshold myopic strategy. 
 As mentioned earlier, in general determining the 
optimal strategy for $X>2$ is computationally intractable. However, for the high SNR case, we will show below that a
 threshold strategy yields near optimal behavior.
 
 \begin{theorem}
Assume (A1),(A2) and (A5)-(i) hold. Then for perfect observations, the optimal sampling strategy, denoted
$\mu^*(x)$,
 is a threshold. Therefore by Corollary \ref{cor:kl}, for
optimal sampling with Gaussian noise with variance $\epsilon^2$, the threshold sampling strategy $\mu^*(x)$ 

\end{theorem}



 
 
 
 
\subsection{Optimality of Threshold Policies in High SNR}
For $X=2$, Theorem \ref{thm:main1} showed that the optimal sampling strategy was a threshold. However, 
 for $X>2$, we only showed in Theorem \ref{thm:myopic} that the optimal strategy is lower bounded by a threshold myopic strategy. In general determining the 
optimal strategy for $X>2$ is computationally intractable. However, for the high SNR case, we will show below that the optimal sampling
strategy is indeed
a threshold strategy.

We start with the case where perfect observations of the Markov state are available at sampling times. Note that the problem is still a POMDP
 since between sampling times, the belief state needs to be computed.
We start with the following fairly obvious result.  It will be used to characterize the optimality of threshold strategies when perfect
observations of the state are available.



\begin{theorem} \label{thm:obvious} Suppose perfect observations of the state are made at decision times $\tau_k$, $k=1,2,\ldots$
according to the protocol of Sec.\ref{sec:qdmodel}. Assume the initial
belief state
$\pi_0 = e_i$, $i \in \mathbb{X}$.
Then: \\
(i) At each time $k$ the belief state $\pi_k$ generated by (\ref{eq:hmm})  lies in one of $X-1$ trajectories, denoted $\boldsymbol{\pi}_i$, $i=1,2,\ldots,X-1$.
Trajectory $\boldsymbol{\pi}_i$ comprises of the infinite sequence of belief states 
\begin{equation} \boldsymbol{\pi}_i = \{e_i,A^\prime e_i, {A^\prime }^2 e_i, \ldots \}, \quad i=1,2,\ldots,X-1  \label{eq:traj} \end{equation}
initialized at unit vector $e_i$. Furthermore if $A$ is aperiodic and irreducible, then each trajectory converges to the stationary distribution
of $A$.\\
(ii) If $A \succeq A^2$ (where $\succeq$ is defined in (\ref{eq:mor})), then each trajectory $\boldsymbol{\pi}_i$ comprises of MLR decreasing elements. That is $A^\prime e_i \geq_r {A^\prime}^2 e_i 
\geq_r {A^\prime}^3 e_i \geq_r \cdots $. \qed
\end{theorem}

With the above result, we can now state the following main result of this section.

\begin{framed}
\begin{theorem} Assume the conditions of Theorem  \ref{thm:obvious}.
 Suppose perfect observations of the state are made at decision times $\tau_k$, $k=1,2,\ldots$ according to the protocol of Sec.\ref{sec:qdmodel}.  Then\\
 (i) Under (A1), (A2), (A4), the optimal sampling strategy $\mu^*(\pi)$ is MLR increasing in $\pi$. That is,
 $\pi \geq_r {\bar{\pi}} \implies \mu^*(\pi) \geq \mu^*({\bar{\pi}})$.\\
 (ii) As a consequence, on each trajectory $\boldsymbol{\pi}_i$ there are up to $L$ threshold  states denoted
 $\pi^*_{i,l}$, $l=1,2,\ldots,L-1$. These thresholds  $\pi^*_{i,l}$  are MLR increasing in $l$.
 The optimal sampling strategy is a threshold: For belief state $\pi$ in  trajectory $\boldsymbol{\pi}_i$, $i=1,\ldots,X-1$,
 \begin{equation}  \mu^*(\pi) = \begin{cases}
 0 \text{ (stop) } & e_1 \leq_r \pi \leq_r \pi^*_{i,0} , \\
 u ,  & \pi^*_{i,u-1} \leq_r \pi \leq_r \pi^*_{i,u} , \quad u \in \{1,2,\ldots,L\}  \end{cases} \label{eq:seqstrategy}
 \end{equation}
 So there are a total of $(X-1)L$ threshold belief states in the $X-1$ trajectories.
 \end{theorem}
\end{framed}


The above theorem deals with perfect observations (infinite signal to noise ratio). What happens for small noise of order $\epsilon$?
The following result shows that applying the threshold strategy (\ref{eq:seqstrategy}) to the small noise case yields an optimal cost
within $O(\epsilon)$ of the optimal cost of the small noise case. Therefore for high SNR, a threshold strategy
is $\epsilon$-optimal.

\end{comment}






\subsection{Stochastic Dominance Properties of  the Bayesian Filter}
 \label{sec:filter}
 This section presents  structural properties of the 
Bayesian filter  (\ref{eq:hmm}) which determines the evolution of the  belief state $\pi$.
Indeed, the proofs of Theorems \ref{thm:main1}-\ref{thm:sens} presented in previous sections
depend on Theorem \ref{thm:filter} given below.
 The results in Theorem \ref{thm:filter} are also of independent interest in Bayesian filtering and prediction.
To compare posterior distributions of Bayesian filters we need to introduce stochastic orders.
We first start with some background definitions.

\subsubsection{Stochastic Orders}
 In order to compare  belief states
we will use the monotone likelihood ratio (MLR)
stochastic order.
 
\begin{definition}[MLR ordering, \cite{MS02}]
Let $\pi_1, \pi_2 \in \Pi(X)$ be any two belief state vectors.
Then $\pi_1$ is greater than $\pi_2$ with respect to the MLR ordering -- denoted as
$\pi_1 \geq_r \pi_2$,
 if 
\begin{equation} \pi_1(i) \pi_2(j) \leq \pi_2(i) \pi_1(j), \quad i < j, i,j\in \{1,\ldots,X\}. 
\label{eq:mlrorder}\end{equation}
\end{definition}
Similarly $\pi_1 \leq_r \pi_2$ if  $\leq$ in (\ref{eq:mlrorder}) is replaced
by a $\geq$. \\
The MLR stochastic order is  useful  since it is closed  under conditional expectations.
That is, $X\geq_r Y$  implies $\E\{X|\mathcal{F}\} \geq_r \E\{Y|\mathcal{F}\}$ for any two random variables $X,Y$ and sigma-algebra $\mathcal{F}$
 \cite{Rie91,KR80,Whi82,MS02}. 

\begin{definition}[First order stochastic dominance, \cite{MS02}]
 Let $\pi_1 ,\pi_2 \in \Pi(X)$.
Then $\pi_1$ first order stochastically dominates $\pi_2$  -- denoted as
$\pi_1 \geq_s \pi_2$ --
 if 
$\sum_{i=j}^X \pi_1(i) \geq \sum_{i=j}^X \pi_2(i)$  for $ j=1,\ldots,X$.
\end{definition}

The following result is well known \cite{MS02}. It says that MLR dominance implies first order stochastic dominance and gives a necessary and sufficient
condition for stochastic dominance.
\begin{theorem}[\cite{MS02}] \label{res1}
 (i)  Let $\pi_1 ,\pi_2 \in \Pi(X)$.
Then $\pi_1 \geq_r \pi_2$ implies $\pi_1\geq_s \pi_2$.\\
(ii) Let $\mathcal{V}$ denote the set of all $X$ dimensional vectors
$v$ with 
 nondecreasing components, i.e., $v_1 \leq v_2 \leq \cdots
v_X$.
Then $\pi_1 \geq_s \pi_2$ iff for all $v \in \mathcal{V}$,
 $v^\prime \pi_1 \geq v^\prime \pi_2$. 
\end{theorem}



For state-space dimension $X =2$, MLR is a complete order and coincides with
first order stochastic dominance.
For state-space dimension $X >2$,
MLR is a  {\em partial order}, i.e., $[\Pi(X),\geq_r]$ is a partially ordered set (poset) since it is not always
possible to order any two belief states $\pi \in \Pi(X)$.

\subsubsection{Main Result} With the above definitions, we are now ready to state the main result regarding the stochastic dominance
properties of the Bayesian filter.
\begin{framed}
\begin{theorem}  \label{thm:filter} The following structural properties hold for the Bayesian filtering update $T(\pi,y,u)$ and
normalization measure $\sigma(\pi,y,u)$ defined in (\ref{eq:hmm}):
\begin{enumerate}
\item 
Under (A2), $\pi_1 \geq_r \pi_2$ implies   $T(\pi_1,y,u)\geq_r T(\pi_2,y,u)$ holds.
\item Under (A2) and (A3),  $\pi_1 \geq_r \pi_2$ implies   the normalization measure satisfies
 $\sigma(\pi_1,\cdot,u) \geq_s \sigma(\pi_2,\cdot,u)$.
 \item Under (A3) and (A5-(i)), the normalization measure $\sigma(\pi,\cdot,u)$ satisfies the following submodular property:
$$\sum_{y\geq \bar{y}}\left[ \sigma(\pi,y,u+1)  - \sigma(\pi,y, u)\right]
 \leq \sum_{y\geq \bar{y}} \left[\sigma({\bar{\pi}},y,u+1)  - \sigma({\bar{\pi}},y, u)\right] \text{ for } \pi \geq_r{\bar{\pi}}$$
\item 
For $y,\bar{y} \in \mathbf{Y}$,  $y > \bar{y}$ implies $T(\pi_1,y,u)\geq_r T(\pi_1,\bar{y},u)$ iff 
(A3) holds.
\item Consider the ordering of transition matrices $A \succeq \bar{A}$ defined in (\ref{eq:mor}).
\begin{enumerate}
\item If $A \succeq \bar{A}$ then ${A}^\prime \pi \geq_r {\bar{A}}^\prime \pi$, that is, the one-step Bayesian predictor with transition matrix
$A$ MLR dominates that with transition matrix $\bar{A}$.
\item If  $A \succeq \bar{A}$ and (A2) holds, then $({A^l})^\prime \pi \geq_r ({\bar{A}^l})^\prime \pi$ for any positive integer $l$. That is, the $l$-step Bayesian predictor preserves this MLR dominance.
\end{enumerate}
\item Let  $T(\pi,y,u;A)$ and $\sigma(\pi,y,u;A)$ denote, respectively, the Bayesian filter update and normalization measure
using transition matrix $A$.  Then they satisfy the following stochastic dominance property with respect to 
the ordering of $A$ defined in (\ref{eq:mor}):
\begin{enumerate}
\item   $A \succeq \bar{A}$  implies $T(\pi,y,u;A) \geq_r T(\pi,y,u;\bar{A})$.
\item
 Under  (A3), $A \succeq \bar{A}$ implies $\sigma(\pi,\cdot,u;A) \geq_s \sigma(\pi,\cdot ,u;\bar{A})$. 
\end{enumerate}
\end{enumerate}
\end{theorem}
\end{framed}
In words, 
Part~1 of the theorem implies that the Bayesian filtering recursion preserves the MLR ordering providing that  the transition matrix is TP2
(A2).  Part~2 says that the normalization measure  preserves first order stochastic dominance providing (A2) and (A3) hold. 
Part~3 shows that the normalization measure is submodular. This is a crucial property in establishing Theorem~\ref{thm:main1}.
Part~4 shows
that under (A3), the larger the observation value, the larger  the posterior distribution (wrt MLR order). 
 Part~5 shows that if starting with two different transition matrices but identical priors, then the optimal predictor with the larger transition matrix
 (in terms of the order introduced in (\ref{eq:mor})) MLR dominates the predictor with the smaller transition matrix.
Part~6 says that same thing about the filtering recursion $T(\pi,y,u)$ and the normalization measure~$\sigma(\pi,y,u)$.





\section{Numerical Examples} \label{sec:numerical}

{\em Example 1. Optimal Sampling  Quickest Detection with Binary Erasure Channel measurements}:
Consider $X=2,Y=3, L=5$, $f=17$, $d=0.4$, $m(e_i,1) = 0$, $m(e_i,2) = 2.8$,
$$   \{D_1,D_2,D_3,D_4\}  = \{1, 3, 5, 10 \},\;
A = \begin{bmatrix} 1 & 0 \\ 0.1 & 0.9  \end{bmatrix}, \; B = \begin{bmatrix}
0.3 & 0.7 & 0 \\ 0 & 0.2 & 0.8 \
\end{bmatrix} $$
The noisy observations of the Markov chain specified by observation probabilities $B$ models a binary non-symmetric erasure channel
\cite{CT06}.
Note that a binary erasure channel is TP2 by construction (all second order minors are non-negative) and so (A3) holds.


 The optimal strategy was computed by forming a grid of 1000 values in the 2-dimensional unit simplex, and then solving the value iteration algorithm 
 (\ref{eq:vi}) over this grid on a horizon $N$ such that $\sup_{\pi} |V_N(\pi) - V_{N-1}(\pi) | < 10^{-6}$.
Figure
 \ref{fig:thm1}(a) shows that when the conditions of Theorem \ref{thm:main1} are satisfied, the strategy is monotone decreasing in
 posterior $\pi(1)$.
To show that the sufficient conditions of Theorem \ref{thm:main1} are useful, Figure
 \ref{fig:thm1}(b) gives an example of when these conditions do not hold, the optimal strategy is no longer monotone.
 Here  $m(e_i,1) = 2.8$, $m(e_i,2) = 0$ and therefore violates (A1) of Theorem \ref{cor:qd}.
 
 
 {\em Example 2. Optimal Sampling Quickest Detection  with Gaussian noise measurements}:
Here we consider identical parameters
to Example 1 except that the observation distribution is Gaussian with $B_{1y} \sim N(1,1)$, $B_{2y} \sim N(2,1)$
and measurement costs are  $m(e_i,u) = 1$ for all $i\in \mathbb{X}, u \in \{1,2,3,4\}$.
Since the measurement cost is a constant (A1) and (A4) of Theorem~\ref{cor:qd} hold trivially. As mentioned in Sec.\ref{sec:discussion},
(A3) holds for Gaussian distribution. Therefore Theorem \ref{cor:qd} applies and the optimal strategy $\mu^*(\pi)$ is monotone
decreasing in $\pi(1)$.
Fig.\ref{fig:gp} illustrates the optimal strategy.  
Next, using Theorem \ref{cor:qd2}, the myopic strategies $\bar{\mu}(\pi)$  forms an upper bound
to the optimal strategy $\mu^*(\pi)$ for actions $u \in \{1,\ldots,4\}$.
 We used $\alpha = f/(d(1 - A_{21})) $ to satisfy (A7)(i)
for the myopic cost in (\ref{eq:bmu}).
 As a bound
 for the optimal stopping
 region, we used the myopic stopping set $\underline{\mathcal{S}}$ defined in~(\ref{eq:ustop}).  These are plotted in Fig.\ref{fig:gp}(a). 



\begin{figure}\centering
\mbox{\subfigure[Gaussian Observation Probabilities]{\epsfig{figure=gaussian.eps,width=0.45\linewidth} } \quad
\subfigure[Poisson Observation Probabilities]{\epsfig{figure=poisson.eps,width=0.45\linewidth} }}
\caption{Optimal sampling strategy for action  $u\in \{0 \text{ (announce change)}, 1, 2, 3, 4\}$ for a quickest-change detection
problem with geometric change time. The parameters are specified in Example 2 and 3 in Sec.\ref{sec:numerical}. The optimal strategy
$\mu^*(\pi)$ is monotone decreasing in $\pi(1)$  and is 
 upper  bounded by myopic strategy $\bar{\mu}$  according to Theorem \ref{cor:qd2}.}
\label{fig:gp}
\end{figure}

{\em Example 3. Optimal Sampling Quickest Detection with Markov Modulated Poisson measurements}:
The parameters here are identical to Example 2 except that the observations are generated by a discrete time Markov Modulated Poisson
process. That is, at each time $k$, observations are generated according to the Poisson distribution 
$B_{xy} =  (\lambda_{x})^{y - 1} \frac{e^{-\lambda_x}}{(y-1)!} $ where the rates $\lambda_1 = 1$, $\lambda_2 = 1.5$. Since (A3) holds
for Poisson distribution, Theorem \ref{cor:qd} applies. Fig.\ref{fig:gp}(b) illustrates the optimal strategy. As in Example 2, the myopic strategy $\bar{\mu}(\pi)$ 
forms an upper  bound.


{\em Example 4. Optimal Sampling with Phase-Distributed Change Time}:
Here we consider optimal sampling quickest detection with PH-distributed change time.
Consider a 3-state ($X=3$) Markov chain observed in noise with parameters $f=10$, $d=0.4$, $m(e_i,u) = 1$, 
$$ A = \begin{bmatrix}  1 & 0 & 0 \\  0.7 & 0.3 & 0 \\  0.3 & 0.4 & 0.3 \end{bmatrix},
B =  \begin{bmatrix} 0.8 & 0.2 & 0 \\  0.1 & 0.8 & 0.1\\  0 & 0.1 & 0.9 \end{bmatrix},  
\{D_1,D_2,D_3,D_4\} = \{1, 2, 4, 5\}.$$
So $\Pi(X)$ is a 2-dimensional unit simplex.
The optimal strategy was computed by forming a grid of 8000 values in the 2-dimensional unit simplex, and then solving the value iteration algorithm 
 (\ref{eq:vi}) over this grid on a horizon $N$ such that $\sup_{\pi} |V_N(\pi) - V_{N-1}(\pi) | < 10^{-6}$. Fig.\ref{fig:myopic}(a) shows the optimal strategy.
 
 It can be verified that the transition matrix $A$ satisfies (A3), (A6) and (A7) for $\alpha = 100$. Also the observation
 distribution $B$ satisfies (A2). 
Therefore Theorem \ref{cor:qd2}  holds and the optimal strategy is upper
 bounded by the myopic strategy $\bar{\mu}(\pi)$ defined in (\ref{eq:bmu}). Fig. \ref{fig:myopic}(b) shows the myopic strategy $\bar{\mu}(\pi)$. As a bound
 for the optimal stopping
 region, we used the myopic stopping set $\underline{\mathcal{S}}$ defined in~(\ref{eq:ustop}). In Fig.\ref{fig:myopic}(b) these are represented by `0'.

\begin{figure}\centering
\mbox{\subfigure[Optimal Policy $\mu^*(\pi)$]{\epsfig{figure=fig3state.eps,width=0.45\linewidth} } \quad
\subfigure[Myopic Upper Bound  $\bar{\mu}(\pi)$]{\epsfig{figure=myopic.eps,width=0.45\linewidth} }}
\caption{Optimal sampling strategy for action  $u\in \{0 \text{ (announce change)},  1 , 2, 3, 4\}$ for a quickest-change detection
problem with PH-distributed time specified by 3-state Markov chain in Example 4 of Sec.\ref{sec:numerical}. The belief space $\Pi(X)$ is a two dimensional
unit simplex (equilateral triangle). The optimal strategy
is upper bounded by myopic strategy $\bar{\mu}(\pi)$  according to Theorem \ref{cor:qd2}.}
\label{fig:myopic}
\end{figure}


\section{Discussion} \label{sec:conclusions}
The paper presented  structural results for the optimal sampling strategy of a Markov chain  given noisy measurements.
An example dealing with  quickest change detection with optimal sampling was discussed to motivate the main results.
Such problems are instances of partially observed Markov decision processes (POMDPs) and computing the optimal sampling strategy is 
intractable in general. However, this paper shows that  under reasonable conditions on the sampling costs, transition matrix and 
noise distribution, one can say a lot about the optimal strategy and achievable cost using tools in stochastic dominance and lattice
programming.
There main results were:  Theorems  \ref{thm:main1} and \ref{cor:qd} gave sufficient conditions for the existence of a monotone
optimal sampling strategy (with respect to
the posterior distribution) when the underlying Markov chain had two states. It justified the intuition that one should
make measurements less frequently when the underlying state is away from the target state. Theorem \ref{thm:myopic} and Theorem
\ref{cor:qd2} gave sufficient
conditions for the myopic sampling strategy to form a lower bound or upper bound to the optimal sampling strategy for multi-state Markov chains.
Theorem \ref{thm:tmove} gave a partial ordering for the transition matrix and noise distributions so that the expected cost 
of the optimal sampling strategy decreased as these parameters increased. This yields useful information on the achievable optimal cost
of an otherwise intractable problem.  Theorem \ref{thm:sens}, gave explicit bounds on the sensitivity of the total sampling cost with respect to sampling
strategy in terms of the Kullback Leibler divergence between the noise distributions.  
Theorem \ref{thm:filter} gave several useful structural properties of the optimal Bayesian filtering update including sufficient conditions that preserve monotonicity of the filter with observation, prior distribution, transition matrix and noise
distribution. 

The assumptions (A1-A7) used in this paper are set valued; so even if the precise
parameters (transition probabilities, observation distribution, costs)  are not known, as long as they belong to the appropriate sets, the structural results hold. Thus the results have an inherent robustness.


Finally, it is interesting to note that the results derived in this paper  on sampling control do not apply to 
general  measurement control problems where
 the action affects the observation distribution rather than transition kernel.  The reason is that it is not possible to find two non-trivial stochastic matrices (kernels)
 $B$ and $\bar{B}$ such that the belief updates satisfy  (i) $T(\pi,y;B) \geq_r T(\pi,y;\bar{B})$ and normalization
 measure satisfies (ii) $\sigma(\pi,\cdot,B) \geq_s \sigma(\pi,\cdot;\bar{B})$. In \cite{Lov87}, it is claimed that if $B$ TP2 dominates $\bar{B}$ then
 (i) and (ii) hold. However, we have found that  the only examples of stochastic kernels that satisfy the TP2 dominance are the trivial exampl
  $B = \bar{B}$.
 In our paper, which deals with sampling control, the ordering (\ref{eq:mor}) was  constructed so  that two transition matrices $A$ and $\bar{A}$ satisfy (i) and (ii) with $B,\bar{B}$
 replaced by $A, \bar{A}$. This ordering
 was used in Assumption (A6). 
 
 


