\section{Characterizations of Optimal Policies}  \label{sec:characterization}


We begin by studying structural properties of optimal policies, which can be exploited to identify optimal actions using well-designed {\em opening thresholds}. In Section~\ref{sec:stopping}, we show that it is optimal to stop when the largest available prize exceeds all opening thresholds.
In Section~\ref{sec:F_largest}, we establish that whenever the largest opening threshold corresponds to an F-opening action, it is optimal to F-open the corresponding box.
In contrast, we show that the complementary case, in which the largest opening threshold corresponds to a P-opening action, is more complex to analyze, as there exists no threshold-based decision rule that is universally optimal. Nevertheless, in Section~\ref{sec:P_largest}, we identify sufficient conditions for which P-opening the box with the largest threshold is optimal.
In Section~\ref{sec:optimal_binary_prize_iid}, we provide a complete characterization of the optimal policy for a special case of a PSI with binary prizes where partial opening  reveals two types. 




\subsection{Opening thresholds and optimal stopping rule} \label{sec:stopping}
We start by defining \textit{opening thresholds}, a type of index associated with each potential action. 
Although there may not exist an optimal index policy (as shown in Section~\ref{subsec:motivating_examples}), we show that such indices explain to a large degree the optimal policy. 
While applicable to general system states, the thresholds can be most easily illustrated by considering the special case where there is a single box that is not fully open. This setting also allows us to express the optimal stopping criterion using our thresholds. 
We let $x^+ = \max\{0,x\}$ for every $x\in \mathbb{R}$.


\begin{definition}[Thresholds]\label{def:testing_threshold}
 For every box $i \in [N]$, we define the opening thresholds:
\begin{itemize}
    \item If box $i$ is closed, the F-threshold $\sigma^{F}_i$ is a solution to
    \begin{equation}  \label{eq:def_F_threshold}
      c_i^F = \mathbb{E}_{V_i}\Big[(V_i-\sigma^{F}_i)^+\Big].
    \end{equation}

    \item If box $i$ is partially opened with type $t_i$, the (conditional) F-threshold $\sigma^{F \mid t_i}_i$ is a solution to
    \begin{equation} \label{eq:def_F_threshold_partial}
      c_i^F = \mathbb{E}_{V_i \mid T_i=t_i}\Big[(V_i - \sigma^{F \mid t_i}_i)^+\Big]. 
    \end{equation}

    \item If box $i$ is closed, the P-threshold $\sigma^{P}_i$ is a solution to
\begin{equation} \label{eq:def_P_threshold}
  c_i^P = \mathbb{E}_{T_i} \Big[\max\{0, -c_i^F + \mathbb{E}_{V_i \mid T_i} \big[ (V_i-\sigma^{P}_i)^+ \big]\}\Big].  
\end{equation}

    \item If box $i$ is closed, the FP-threshold $\sigma^{F/P}_i$ is a solution to
\begin{equation}
c_i^P = \mathbb{E}_{T_i} \Big[\max\{0, c_i^F-\mathbb{E}_{V_i \mid T_i} \big[ (V_i-\sigma^{F/P}_i)^+ \big]\}\Big].  
\end{equation}
Observe that the threshold is well-defined even in the case that $c_i^P \geq c_i^F $, in which case P-opening is not beneficial.
\end{itemize}
\end{definition}



Assuming the prize distributions are non-atomic, it is not difficult to see that the above thresholds $\sigma_i^F$, $\sigma_i^{F \mid t_i}$, $\sigma_i^P$, and $\sigma_i^{F/P}$ exist and are uniquely defined.
Moreover, there is a natural ordering between threshold values:


\begin{observation}[Thresholds order]\quad\label{obs:thresholds_order}
    \begin{enumerate}
    \item For any box $i$, either $ \sigma^{F/P}_i = \sigma^{F}_i = \sigma^{P}_i$,  $ \sigma^{F/P}_i < \sigma^{F}_i \leq \sigma^{P}_i$, or $ \sigma^{P}_i \leq \sigma^{F}_i < \sigma^{F/P}_i$; 
    \item For any box $i$, we have $\underset{t_i \in \Gamma_i}{\min} ~ \sigma_{i}^{F|t_i} \leq \sigma_i^{F/P}$ and $\underset{t_i \in \Gamma_i}{\max} ~\sigma_{i}^{F|t_i}  \geq \sigma_i^P$. 
    \end{enumerate}
\end{observation}




\paragraph{Economic interpretation.}
The set of F-thresholds $\{\sigma_i^{F}\}$ in Equation~\eqref{eq:def_F_threshold} describes the optimal index policy for the standard Pandora's box problem \citep{weitzman1979optimal}. 
The conventional economic interpretation for this opening threshold is that of a fair strike price of a hypothetical option contract. That is, if $c_i^F$  is the cost of a call option to buy prize $V_i$ with strike price $\sigma_i^{F}$, then $\sigma_i^{F}$ is the ``fair'' strike price that equalizes the cost and the expected profit of buying this option. 
 {This intuition carries over to our problem where inspections are sequential using the notion of a compound option or, informally, a ``two-stage call option.'' This analogy is developed in Appendix~\ref{apx:economic_interpretation}.}





\paragraph{Single-box setting and optimal stopping rule.}
We justify our definition of the opening thresholds through their ability to express optimal policies in single closed-box settings, and to prescribe an optimal stopping rule in  general.
Namely, the \textit{single closed-box setting} is the collection of states $({\cal C},{\cal P},y)$  where there is only one closed box that can be inspected, i.e., $\mathcal{C}=\{ i\}$  for some box $i\in [N]$ and $\mathcal{P}=\emptyset$.
The difference between the expected profit from F-opening and from stopping is exactly
\begin{equation} \label{eq:optimal_stopping_F}
    -c_i^F + \mathbb{E}_{}\Big[\max \left \{ V_i, y \right \}\Big] - y  = -c_i^F + \mathbb{E}_{}\Big[ \max \{ V_i - y, 0  \} \Big] = - \mathbb{E}_{}\Big[ \max \{ V_i - \sigma_i^F, 0  \} \Big] +  \mathbb{E}_{}\Big[ \max \{ V_i - y, 0  \} \Big] \ . 
\end{equation}

The F-threshold can be therefore interpreted as a break-even point for the value of $y$ under which F-opening is preferred to stopping, and over which stopping is preferred.
Similarly, in this single-box case, the difference between the expected profit from P-opening (and following the optimal action thereafter) and from stopping is
\begin{eqnarray}
 & &  - c_i^P + \mathbb{E}_{T_i} \Big[\max\{ y , -c_i^F + \mathbb{E}_{V_i \mid T_i} \big[ \max \left\{ V_i , y \right\} \big]\} \Big] - y \nonumber \\
 &=&  - c_i^P + \mathbb{E}_{T_i} \Big[\max\{0, -c_i^F + \mathbb{E}_{V_i \mid T_i} \big[ \max \left\{ V_i - y , 0 \right\} \big]\} \Big] \nonumber \\ 
 &=& - \mathbb{E}_{T_i} \Big[\max\{0, -c_i^F + \mathbb{E}_{V_i \mid T_i} \big[ (V_i-\sigma^{P}_i)^+ \big]\}\Big] + \mathbb{E}_{T_i} \Big[\max\{0, -c_i^F + \mathbb{E}_{V_i \mid T_i} \big[ \max \left\{ V_i - y , 0 \right\} \big]\} \Big].
 \label{eq:optimal_stopping_P}  
\end{eqnarray} 

Similarly, the P-threshold can be interpreted as a break-even point for the value of $y$ under which P-opening is preferred to stopping, and over which stopping is preferred.


Regarding the FP-threshold $\sigma^{F/P}_i$, we note that the difference between the expected profits from the optimal course of actions starting from P-opening box $i$ and that from the optimal course of actions starting from F-opening box $i$ is 
\begin{eqnarray}
 & & \left( - c_i^P + \mathbb{E}_{T_i} \Big[\max\left\{y, -c_i^F + \mathbb{E}_{V_i \mid T_i} \big[ \max \left\{ V_i , y \right\} \big]\right\} \Big]  \right) - \left(-c_i^F + \mathbb{E}_{}\Big[\max \left\{ V_i, y \right\}\Big]\right)    \nonumber\\
 &&=  - c_i^P + \mathbb{E}_{T_i} \Big[\max\{0, c_i^F-\mathbb{E}_{V_i \mid T_i} \big[ (V_i-y)^+ \big]\}\Big] \ . \label{eq:optimal_stopping_FP}
\end{eqnarray}

One can verify that the threshold $\sigma_{i}^{F/P}$ is a break-even point on the value of $y$ that determines whether P-opening or F-opening achieves a higher expected profit. 
Intuitively, in the single-box case, the definition for the set of thresholds $\sigma_i^F$, $\sigma_i^{F \mid t_i}$, $\sigma_i^P$, and $\sigma_i^{F/P}$ exploits the single-crossing property between pairs of action-value functions. In the more general case, the definition can be viewed as using a myopic approximation for the action-value functions that assumes that only one box may be opened.



Based on the above discussion, we construct a natural \textit{threshold-based policy} for the single closed box setting. 
We assign the index $y$ to the action of stopping, the index $\sigma_i^P$ to the action of P-opening, and the index $ \sigma^{F}_{i}$ to the action of F-opening. 
Our policy prescribes which action to take by comparing their corresponding indices.
If the largest threshold is $y$,  then we stop and choose the largest prize at hand. Otherwise, if the largest threshold is $\sigma^F_i$, then we $F$-open box $i$ and choose the largest prize at hand. Finally, if the highest threshold is $\sigma^P_i$, we compare $y$ to $\sigma^{F/P}_i$: if $y\leq \sigma^{F/P}_i$, we F-open, otherwise we P-open box $i$. 
We refer the reader to Figure~\ref{fig:example_1} for a pictorial illustration; the policy is also summarized as Algorithm~\ref{algo:single-box} in Appendix~\ref{appendix:thm_stopping}. 



The next theorem states the optimality of our threshold-based rules in the single close box setting. Moreover, in the general case (where there is more than one box), the same threshold-based logic yields an optimal stopping criterion.
For any event $A$, we let $\BFI\{A\}$ denote the indicator function that equals $1$ if $A$ occurs and $0$ otherwise. 


We define the largest opening threshold $\sigma_M(\mathcal{C}, \mathcal{P})$:
\begin{equation} \label{eq:sigma_M_C_P}
    \sigma_M(\mathcal{C}, \mathcal{P})  =  \max \left\{  \underset{j \in \mathcal{C} }{\max}  \left\{  \sigma_j^F, \sigma_j^P \right\}, \underset{ j \in \mathcal{P}}{\max }  \left\{ \sigma_j^{F \mid t_j}  \right\}   \right\}. 
\end{equation}
We refer to the box attaining the largest threshold $\sigma_M(\mathcal{C}, \mathcal{P})$ as the {\em leading box}. 

\begin{theorem} \label{thm:myopic_stopping} % [Myopic stopping]
The threshold-based policy is optimal in the single closed box setting $({\cal C},{\cal P},y) = (\{i\}, \emptyset, y)$, and it achieves the following expected profit:
$$
J\left( \{i\}, \emptyset, y \right) = \mathbb{E} \left[ \max \left\{ y,
 \BFI\{ y > \sigma_i^{F/P}  \}  \cdot \min\{V_i, \sigma_i^{F \mid T_i}, \sigma_i^P \} ,
  \BFI\{ y \leq \sigma_i^{F/P}  \} \cdot  \min\{V_i,  \sigma_i^F \}
  \right\} \right].
$$
In general, for every state $(\mathcal{C}, \mathcal{P}, y)$, it is optimal to stop if and only if
\begin{equation}\label{eq:myopic_stopping_condition}
  y \geq \sigma_M(\mathcal{C}, \mathcal{P}) .
\end{equation}

\end{theorem}
The formal proof of the stopping rule is based on a coupling argument, which is presented in Appendix~\ref{appendix:thm_stopping}. 
We argue that the stopping decision regarding a box (i.e., never to open this box in the future) only depends on $y$. Hence, the optimal stopping rule shown for the single box setting holds for the general case. 




\subsection{Sufficient conditions for optimal F-opening} 
\label{sec:F_largest}


Having characterized the optimal stopping criterion, we now focus on states $(\mathcal{C}, \mathcal{P}, y)$ in which stopping is not optimal. 
Here, there are two possibilities: $\sigma_M(\mathcal{C}, \mathcal{P})$  corresponds either to an F-threshold or a P-threshold. The next theorem establishes that in the former case, it is optimal to F-open the leading box. This condition holds regardless of whether the leading box is closed or partially-opened.


\begin{theorem} \label{thm:just_strong}
There exists an optimal policy that immediately F-opens the leading box in every state $(\mathcal{C}, \mathcal{P}, y)$ where stopping is suboptimal and $\sigma_M (\mathcal{C}, \mathcal{P})$ is an F-threshold.
\end{theorem}
The proof of this result appears in Appendix~\ref{appendix:thm_just_strong}. 
The crux of it is constructing a policy that F-opens the leading box, and then showing that this policy achieves a larger expected profit than any alternative one using interchange and coupling arguments. Compared to the standard  Pandora's box problem, 
the main difficulty here is that P-opening introduces more courses of action to consider (e.g., P-open the leading box or alternative ones). Hence, our proof carefully distinguishes between different cases, where the leading box is P-opened and those where it is closed, and proceeds by induction. We need to quantify the value of information gathered by P-opening in order to eventually rule out this option. To this end, we upper bound this quantity using a probabilistic coupling, which exploits the dynamic programming tree locally.

We mention in passing that as part of the proof of the theorem we also show that boxes whose F-threshold is higher than their P-threshold should never be P-opened. The opposite direction does not hold, as our illustrative examples suggest.


\subsection{Sufficient conditions for optimal P-opening} \label{sec:P_largest}

We consider the alternative case where $\sigma_M (\mathcal{C}, \mathcal{P})$ is a P-threshold.  
Not surprisingly, in this case, there is no straightforward decision rule that prescribes the optimal action as a function of the opening thresholds. This was illustrated in Section~\ref{subsec:motivating_examples}, even in the simplest case of a single closed-box where the optimal inspection mode could well be an F-opening or P-opening action, depending on the value of $y$ (we provide another example in Appendix~\ref{subsec:example_many_boxes} that shows the intricacy of optimal policies).  
We identify a sufficient condition under which P-opening the leading box is optimal.



\begin{definition} \label{def:well_class}
   Given a state $(\mathcal{C}, \mathcal{P}, y)$ and a closed box $i \in \mathcal{C}$, we define $
  \sigma_{-i}  = \sigma_M (\mathcal{C}  \setminus \{ i \}, \mathcal{P})  
  $. Suppose $\sigma_i^P > \sigma_i^F $. We say that box $i $ is \textit{well-classified} if $y > \sigma_i^{F/P}$ and for every type $t_i \in \Gamma_i$, one of the following conditions holds: (1) $\sigma_i^{F \mid t_i} \geq \sigma_{-i}$ or (2) $y > \sigma_i^{F \mid t_i}$.
\end{definition}
To unpack this notion, we remark that, when dealing with a well-classified box $i$, there is no ambiguity about the action that follows P-opening.
Put simply, upon P-opening, the box can be classified as  ``good'' or ``bad.''
After observing its type $t_i \in \Gamma_i$, our definition delineates two cases. In
case (1), we infer from Theorem~\ref{thm:just_strong} that it is optimal to immediately F-open the same box (good case), whereas in case (2), we infer from Theorem~\ref{thm:myopic_stopping} that box $i$ will never be F-opened (bad case). Importantly, our notions of ``good'' and ``bad'' types are preserved in later stages of the decision process, regardless of which actions are taken.
As a result, for a well-classified box, it is relatively easier to quantify the  value of information afforded by the P-opening. 
\begin{theorem} \label{thm:just_weak_closed}
There exists an optimal policy that P-opens the leading box in every state $(\mathcal{C}, \mathcal{P}, y)$ where stopping is not optimal, $\sigma_M (\mathcal{C}, \mathcal{P})$ is a P-threshold, and the leading box is well-classified.
\end{theorem}
The proof, presented in Appendix~\ref{appendix:thm_just_weak_closed}, is based on induction using interchange arguments. 
Similarly to Theorem~\ref{thm:just_strong}, the analysis requires a probabilistic coupling of different cases. 


Unfortunately, combining Theorems~\ref{thm:myopic_stopping}, \ref{thm:just_strong}, and \ref{thm:just_weak_closed} does not  determine an optimal policy in every  state of the DP. Unlike the optimal stopping condition, Theorems~\ref{thm:just_strong}-\ref{thm:just_weak_closed} provide sufficient but not necessary conditions. Nevertheless, in Section~\ref{sec:numerical_jay}, we numerically solve synthetic instances and show that these theorems capture optimal decisions in most system states. Theorem~\ref{thm:just_weak_closed} is relatively more useful in ``later stages'' of the decision process, where $y$ tends to be larger, and condition (2) of Definition~\ref{def:well_class} becomes easier to satisfy. 
Moreover, our theorems speed up the DP computation. When the conditions of Theorems~\ref{thm:myopic_stopping}--\ref{thm:just_weak_closed} hold, there is no need to apply the DP recursion.



That said, we identify a special case in which Theorems~\ref{thm:myopic_stopping}--\ref{thm:just_weak_closed} fully characterize an optimal policy. This happens when  every box $i$ such that $\sigma_i^P > \sigma_i^F$, has only two types (i.e., $ |\Gamma_i| = 2 $), and the FP-threshold $\sigma_i^{F/P}$ is negative (i.e., $\sigma_i^{F/P} < 0$).
To see this, note that whenever stopping is suboptimal, we have two cases: If the largest opening threshold is an F-threshold, it is optimal to F-open the leading box (Theorem~\ref{thm:just_strong}). If the largest threshold is a P-threshold, then the leading box $i$ is well-classified. Indeed, in view of the discussion that follows Definition~\ref{def:testing_threshold}, we know that $ \underset{t_i \in \Gamma_i}{\min} ~ \sigma_{i}^{F|t_i} \leq \sigma_i^{F/P} < 0 \leq y  $ and $\underset{t_i \in \Gamma_i}{\max} ~ \sigma_{i}^{F|t_i} \geq \sigma_i^P > \sigma_{-i}$. Intuitively, this setting captures scenarios in which alternatives can be either very good or very bad. If partial opening is cheap enough, it should always be exercised. 
We summarize this fact in the next corollary. 
\begin{corollary} \label{cor:support_2}
Suppose that every box $i \in [N]$ such that $\sigma_i^P > \sigma_i^F$ satisfies $ |\Gamma_i| = 2 $ and $\sigma_i^{F/P} < 0$. Then, Theorems~\ref{thm:myopic_stopping}, \ref{thm:just_strong} and \ref{thm:just_weak_closed} fully determine an optimal policy. 
\end{corollary}



\subsection{An optimal policy for a problem with binary prizes} \label{sec:optimal_binary_prize_iid}

\input{main_body/two_boxes.tex}







