
%\noindent Electronic Companion
%\begin{center}
\noindent {\Huge\bfseries Electronic Companion}
%\end{center}

\vspace{1em}
\section{Example~\ref{example:many_boxes}}
\label{subsec:example_many_boxes}
We construct an additional example which provides further evidence about the intricacy of the optimal policy in states where the leading threshold corresponds to a P-threshold (see Figure~\ref{fig:example_many_boxes} for a pictorial illustration). 

\begin{example}
\label{example:many_boxes}

We consider the following three boxes: 
\begin{itemize}
    \item Box 1: The opening costs are $c_1^F=1$ and $c_1^P = 0.5$. 
There are two types $\Gamma_1 = \{A,B\}$ and $\p{T_1=A} = 0.2$. 
The joint distribution of $(V_1,T_1)$ is given by: $\p{V_1 = 1 \mid T_1 = A } = 0.1,~ \p{V_1 = 10 \mid T_1 = A } = 0.9$ and $\p{V_1 = 1 \mid T_1 = B } = 0.05, ~\p{V_1 = 10 \mid T_1 = B } = 0.95$.
    \item Box 2: The opening costs are $c_2^F=0.99$ and $c_2^P = 500$. 
There are two types $\Gamma_2 = \{A,B\}$ and $\p{T_2=A} = 0.2$. 
The joint distribution of $(V_2,T_2)$ is given by: $\p{V_2 = 1 \mid T_2 = A } = 0.1, ~\p{V_2 = 10 \mid T_2 = A } = 0.9$ and $\p{V_2 = 1 \mid T_2 = B } = 0.05,~ \p{V_1 = 10 \mid T_1 = B } = 0.95$.
    \item Box 3: The opening costs are $c_3^F=1$ and $c_3^P = 0.5$. 
There are two types $\Gamma_3 = \{A,B\}$ and $\p{T_3=A} = 0.2$. 
The joint distribution of $(V_3,T_3)$ is given by: $\p{V_3 = 1 \mid T_3 = A } = 0.1,~ \p{V_3 = 10 \mid T_3 = A } = 0.9$ and $\p{V_3 = 1 \mid T_3 = B } = 0.05, ~\p{V_3 = 10 \mid T_3 = B } = 0.95$.
\end{itemize}



The thresholds of the boxes are computed numerically and are equal to: $\sigma_1^F = \sigma_3^F \approx 5.45, \sigma_1^P = \sigma_3^P \approx 6.11, \sigma_2^F \approx 5.50, \sigma_2^P < 0$.
The thresholds are visualized in Figure~\ref{fig:example_many_boxes}. 

Depending on the initial state, the unique optimal policy proceeds as follows:
\begin{itemize}
    \item In the initial state of the problem where the only box is box 1, i.e., in state $(\{1\}, \emptyset, 0)$, the optimal policy F-opens box 1.
    \item In the initial state of the problem where there are two boxes, box 1 and box 2, i.e., in state $(\{1,2\}, \emptyset, 0)$, the optimal policy F-opens box 2.
    \item In the initial state of the problem where there are three boxes: box 1, box 2, and box 3, i.e., in state $(\{1,2,3\}, \emptyset, 0)$, the optimal policy P-opens box 1.
\end{itemize}
\end{example}

\begin{figure}[htbp]
  \centering
  \includegraphics[width=9cm]{graphs/example_many_boxes.png}
  % \vspace{-0.2in}
  \caption{Illustration of thresholds in Example~\ref{example:many_boxes}}
  \label{fig:example_many_boxes}
\end{figure}
As evidenced by Example~\ref{example:many_boxes}, the unique optimal policy is not indexable.
More importantly,  and unlike Example~\ref{example:not_indexable}, it shows that the opening priorities may change when boxes are added, even when the value of $y$ remains unchanged:
in state $(\{1\},\emptyset, 0)$, the action of F-opening box~1 is optimal; after adding box 2 (i.e., in state $(\{1, 2\},\emptyset, 0)$), F-opening box 2 becomes optimal, even if the P-threshold of box~1 remains the largest; however, after adding box 3 (which is statistically identical to box 1), the optimal action is to P-open box 1.
In other words, this example shows three states in which $\sigma_1^P$ is the largest threshold but three distinct actions are in fact optimal. 
\\\\\\



\section{Economic interpretation of opening thresholds}
\label{apx:economic_interpretation}


We can use notion of compound option or, informally, a ``two-stage call option,'' to provide an intuitive interpretation for the opening thresholds. This financial instrument refers to a more complex financial contract that allows the buyer to purchase an option at some future date. 
That is, for the price $c_i^P$ the decision-maker can buy the initial (overlying) option, which allows her at a future date (when more information is available) to purchase the second (underlying) option for a price of $c_i^F$. 
The additional information that is available at the time of purchasing the second option is represented by the realization $t_i$.
The conditional F-threshold represents the fair strike price for purchasing $V_i$, given the information that is available at the future date, while the P-threshold represents the strike price for buying the initial option.
This type of option is referred to as Call on Call. 
On the other hand, the FP-threshold corresponds to a compound option which is referred to as Call on Put. It allows the buyer to short an option at a future time. 
That is, in the first stage, the buyer pays $c_i^P$ to observe the type $t_i$, and then decides whether or not to enter the second stage.
In the second stage, she has the right to choose whether to short a call option with prize $V_i$ and a strike price $\sigma_i^{F/P}$. 
Clearly, if the strike price $\sigma_i^{F/P}$ is overpriced, i.e., greater than $\sigma_i^{F \mid t_i}$, a risk-neutral player will sell the second-stage option and otherwise not. 
Therefore, we can interpret $\sigma_i^{F/P}$ as the fair strike price to equalize the expected costs and expected profits of this two-stage option. 



The above interpretation motivates a policy in which the decision maker chooses the highest option strike price---that is, according to the box and opening mode with highest threshold. We show in Section~\ref{sec:stopping} that this index policy is indeed optimal for the single-box case, and we further expand its sufficient optimality conditions in the next sections.





\section{Proofs for Section~\ref{sec:characterization}}
\label{appendix:thm_stopping}

Algorithm~\ref{algo:single-box} below summarizes the optimal policy for the single closed-box setting, which is described in Section~\ref{sec:stopping}.

\begin{algorithm}[H]
\footnotesize
  \caption{The optimal policy for the single closed-box setting.} \label{algo:single-box}
  \begin{algorithmic}[1]
 %  \State Sort the boxes according to $\sigma_i$ s.t. $\sigma_1 \geq \sigma_2 \geq ... \geq \sigma_N$.
  \State Initialize state $(\mathcal{C}, \mathcal{P}, y) \gets (\{ i \}, \emptyset, y)$;
\If{ $y > \max\{ \sigma_i^F, \sigma_i^P \}$}  
    \State Stop and select $y$; 
\ElsIf{ $\sigma_i^F > \max\{ y,\sigma_i^P\}$   }
    \State F-open box $i$, and select the best prize at hand;
\ElsIf{ $\sigma_i^P > \max\{ y,\sigma_i^F\}$}
    \If{ $ y > \sigma_i^{F/P}$}
    \State P-open box $i$;
    \State Then further F-open box $i$ if and only if the realized type $t_i$ is such that $y < \sigma_i^{F \mid t_i}$ or else stop;
    \Else{ }
    \State F-open box $i$, and select the best prize at hand;
    \EndIf
\EndIf
% \label{apx:single-box}
\end{algorithmic}
\end{algorithm}


In what follows we first prove the optimality of the threshold-based policy for the single closed-box case (Section~\ref{apx:single_box}), 
then prove the expression for the expected profit of the optimal policy in the single closed-box case (Section~\ref{apx:single_box_expression}), and finally, prove the optimal stopping condition for the general case (Section~\ref{apx:stopping}). 





\subsection{The optimality of the threshold-based policy for the single closed-box case}\label{apx:single_box}




In state $(\mathcal{C}, \mathcal{P}, y)=(\{i\}, \emptyset, y)$, there are three possible actions that we can take: stop, F-open box $i$ or P-open box $i$.
The optimal stopping rule is argued in Section~\ref{sec:stopping}. We proceed to compare F-opening and P-opening. 
If we F-open the box, then the expected value function is 
\begin{equation}\label{eq:J_A}
    J^F(\{i\}, \emptyset, y) = -c_i^F + \mathbb{E}_{V_i}\big[\max\{y, V_i \}\big] \ . 
\end{equation}
If we P-open the box, we then need to choose between further F-opening and stopping. Therefore, the value function of this course of action is 
\begin{equation}\label{eq:J_B}
  J^P(\{i\}, \emptyset, y) = -c_i^P + \mathbb{E}_{T_i}\bigg[ \max \Big\{y, -c_i^F + \mathbb{E}_{V_i \mid T_i}\big[\max\{y, V_i \}  \big]  \Big\} \bigg] \ . 
\end{equation}

Let $\Lambda_i(y)$ be the set of  ``promising'' types of box $i$ where F-opening is warranted, that is
$$
\Lambda_i(y) := \left\{ t_i \in \Gamma_i  \mid  \sigma_i^{F \mid t_i} > y \right\}= \left \{ t_i \in \Gamma_i  \mid  -c_i^F + \mathbb{E}[(V_i-y)^+ \mid T_i=t_i]>0  \right \} \ .
$$
The difference between F-opening \eqref{eq:J_A} and P-opening and \eqref{eq:J_B} can be written as
\begin{eqnarray}
& &    J^{F}(\{i\}, \emptyset, y) - J^{P}(\{i\}, \emptyset, y)   \nonumber \\ 
 &=& -c_i^F  + \mathbb{E}\big[ \max\{y, V_i \} \big] - \Bigg( -c_i^P + \sum_{T_i \in \Lambda_i(y)} \operatorname{Pr}\big[T_i=t_i\big] \Big( -c_i^F + \mathbb{E}\big[\max\{y, V_i \}  \mid T_i=t_i  \big]  \Big) + \sum_{T_i \notin  \Lambda_i(y)} \operatorname{Pr}\big[T_i=t_i\big] y           \Bigg)  \nonumber \\
   &=&    \sum_{T_i \in \Lambda_i(y)} \operatorname{Pr} \big[T_i=t_i\big]  \Big( -c_i^F+\mathbb{E}\big[ \max\{y, V_i \}  \mid T_i=t_i \big]\Big) + \sum_{T_i \notin \Lambda_i(y)}\operatorname{Pr} \big[T_i=t_i\big]  \Big( -c_i^F+\mathbb{E}\big[ \max\{y, V_i \}  \mid T_i=t_i \big] \Big) \nonumber  \\
   &+& c_i^P + \sum_{T_i \in \Lambda_i(y)} \operatorname{Pr}\big[T_i=t_i\big] \Big( c_i^F - \mathbb{E}\big[\max\{y, V_i \}  \mid T_i=t_i  \big]  \Big)  - \sum_{T_i \notin  \Lambda_i(y)} \operatorname{Pr}\big[T_i=t_i\big] y        \nonumber   \\
   &=& c_i^P + \sum_{T_i \notin  \Lambda_i(y)} \operatorname{Pr}\big[T_i=t_i\big]  \left( \underbrace{-c_i^F+\mathbb{E}\big[  (V_i-y)^+  \mid T_i=t_i \big] }_{\leq 0} \right).   \label{eq:lemma:monotonicity_myopic_gain_SW}
\end{eqnarray}
Using simple arithmetics, one can show that $J^{F}(\{i\}, \emptyset, y) - J^{P}(\{i\}, \emptyset, y)$ is strictly decreasing in $y$. Moreover, the solution to $J^{F}(\{i\}, \emptyset, y) - J^{P}(\{i\}, \emptyset, y) = 0$ is exactly $y=\sigma_i^{F/P}$. 
The optimality of the threshold-based policy for the single-box case then follows from the optimal stopping and the condition about the dominance between F-opening and P-opening, which is determined by the relation between $y$ and $\sigma_i^{F/P}$.



\subsection{The expected profit of the optimal policy in the single closed-box case}\label{apx:single_box_expression}

In what follows, we calculate the expected profit of this optimal policy in closed form. 
\begin{enumerate}
    \item First, if the policy does not stop and F-opens box $i$, the expected profit is
\begin{eqnarray*}
   & & -c_i^F + \operatorname{Pr} \left[ V_i > \sigma_i^F \right] \mathbb{E} \left[ V_i \mid V_i > \sigma_i^F \right]  + \operatorname{Pr} \left[ V_i \leq \sigma_i^F \right]  \mathbb{E} \left[ \max\{y, V_i \}  \mid V_i \leq \sigma_i^F \right]  \\
   &=& \operatorname{Pr} \left[ V_i > \sigma_i^F \right] \sigma_i^F + \operatorname{Pr} \left[ V_i \leq \sigma_i^F \right]  \mathbb{E} \left[ \max\{y, V_i \}  \mid V_i \leq \sigma_i^F \right]    \\
   &=&  \mathbb{E} \left[ \max \left\{y, \min \left\{V_i,  \sigma_i^F \right\}    \right\} \right],
\end{eqnarray*}
where the first equation follows from the definition of F-threshold: $c_i^F = \mathbb{E} \left[ \left( V_i - \sigma_i^F \right)^+   \right] = \operatorname{Pr} \left[ V_i > \sigma_i^F \right] \left( \mathbb{E} \left[ V_i \mid V_i > \sigma_i^F \right] - \sigma_i^F \right)$. Note the terms can be rearranged so that 
$$
-c_i^F + \operatorname{Pr} \left[ V_i > \sigma_i^F \right] \mathbb{E} \left[ V_i \mid V_i > \sigma_i^F \right] = \operatorname{Pr} \left[ V_i > \sigma_i^F \right] \sigma_i^F.
$$
    \item By the same reasoning, following from the definition of the P-threshold $\sigma_i^P$,
\begin{eqnarray*}
  c_i^P &=& \mathbb{E} \Big[\max\{0, -c_i^F + \mathbb{E} \big[ (V_i-\sigma^{P}_i)^+ \mid T_i \big]\}\Big] \\
   &=& \sum_{t_i: \sigma_i^{F \mid t_i} > \sigma_i^P } \operatorname{Pr} \left[ T_i=t_i \right] \Big( -c_i^F + \operatorname{Pr} \left[ V_i > \sigma_i^P \mid T_i=t_i \right]  \left( \mathbb{E}\left[ V_i \mid  V_i > \sigma_i^P, T_i=t_i \right] - \sigma_i^P \right) \Big).
\end{eqnarray*}
Rearranging terms on the right side to the left of the latter equation yields that
\begin{eqnarray}
   & & -c_i^P + \sum_{t_i: \sigma_i^{F \mid t_i} > \sigma_i^P } \operatorname{Pr} \left[ T_i=t_i \right] \Big( -c_i^F + \operatorname{Pr} \left[ V_i > \sigma_i^P \mid T_i=t_i \right] \mathbb{E}\left[ V_i \mid  V_i > \sigma_i^P, T_i=t_i \right] \Big) \nonumber \\
   &=& \sum_{t_i: \sigma_i^{F \mid t_i} > \sigma_i^P } \operatorname{Pr} \left[ T_i=t_i \right]  \operatorname{Pr} \left[ V_i > \sigma_i^P \mid T_i=t_i \right] \sigma_i^P \ .  \label{eq:single_box_P_open}
\end{eqnarray}

Therefore, if the policy does not stop and P-opens box $i$ first, the expected profit is
\begin{eqnarray*}
   & &  -c_i^P + \sum_{t_i: \sigma_i^{F \mid t_i} > \sigma_i^P } \operatorname{Pr} \left[ T_i=t_i \right] \Big ( -c_i^F + \operatorname{Pr} \left[ V_i > \sigma_i^P \mid T_i=t_i \right] \mathbb{E}\left[ V_i \mid  V_i > \sigma_i^P, T_i=t_i \right]  \\
   & & \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad   +   \operatorname{Pr} \left[ V_i \leq \sigma_i^P  \mid T_i=t_i\right]  \mathbb{E} \left[ \max\{ y, V_i \}   \mid V_i \leq \sigma_i^P, \sigma_i^{F \mid t_i} > \sigma_i^P  \right] \Big)     \\
   & & + \sum_{t_i: \sigma_i^{F \mid t_i} \leq \sigma_i^P } \operatorname{Pr} \left[ T_i=t_i \right] \left(  \BFI \left\{  y > \sigma_i^{F \mid t_i} \right\} \cdot y +    \BFI \left\{  y \leq \sigma_i^{F \mid t_i} \right \} \left( -c_i^F + \mathbb{E} \left[ \max\{y, V_i\} \mid y \leq \sigma_i^{F \mid t_i},  \sigma_i^{F \mid t_i} \leq \sigma_i^P  \right] \right)    \right)      \\
   &=& \sum_{t_i: \sigma_i^{F \mid t_i} > \sigma_i^P } \operatorname{Pr} \left[ T_i=t_i \right] \Big( \operatorname{Pr} \left[ V_i > \sigma_i^P \mid T_i=t_i \right] \sigma_i^P +  \operatorname{Pr} \left[ V_i \leq \sigma_i^P  \mid T_i=t_i\right]  \mathbb{E} \left[ \max\{ y, V_i \}   \mid V_i \leq \sigma_i^P, \sigma_i^{F \mid t_i} > \sigma_i^P  \right]   \Big) \\
   & & + \sum_{t_i: \sigma_i^{F \mid t_i} \leq \sigma_i^P } \operatorname{Pr} \left[ T_i=t_i \right]  \left(\BFI \left\{  y > \sigma_i^{F \mid t_i} \right\} \cdot y +  \BFI \left\{  y \leq \sigma_i^{F \mid t_i} \right \}   \mathbb{E} \left[ \max \{ y, \min \{ V_i, \sigma_i^{F \mid t_i} \} \} \mid y \leq \sigma_i^{F \mid t_i},  \sigma_i^{F \mid t_i} \leq \sigma_i^P  \right]   \right)    \\
   &=& \mathbb{E} \left[ \max \left\{ y, \min\{V_i, \sigma_i^{F \mid T_i}, \sigma_i^P \}
  \right\} \right].
\end{eqnarray*}
Here, the first equality follows by introducing \eqref{eq:single_box_P_open} and using the definition of F-threshold again. Indeed, for a type $t_i$ such that $y \leq \sigma_i^{F \mid t_i} \leq \sigma_i^P$, $c_i^F = \p{V_i > \sigma_i^{F \mid t_i} } \E{ V_i - \sigma_i^{F \mid t_i} \mid V_i > \sigma_i^{F \mid t_i}, y \leq \sigma_i^{F \mid t_i} \leq \sigma_i^P}$. Therefore, we have 
\begin{small}
\begin{eqnarray*}
    & & -c_i^F + \mathbb{E} \left[ \max\{y, V_i\} \mid y \leq \sigma_i^{F \mid t_i},  \sigma_i^{F \mid t_i} \leq \sigma_i^P  \right]  \\
    &=& - \p{V_i > \sigma_i^{F \mid t_i} } \E{ V_i - \sigma_i^{F \mid t_i} \mid V_i > \sigma_i^{F \mid t_i}, y \leq \sigma_i^{F \mid t_i} \leq \sigma_i^P} \\
    & & + \p{V_i > \sigma_i^{F \mid t_i} } \mathbb{E} \left[ V_i \mid V_i > \sigma_i^{F \mid t_i} ,  y \leq \sigma_i^{F \mid t_i},  \sigma_i^{F \mid t_i} \leq \sigma_i^P  \right] 
    + \p{V_i \leq \sigma_i^{F \mid t_i} } \mathbb{E} \left[ \max\{y, V_i\} \mid V_i \leq \sigma_i^{F \mid t_i} ,  y \leq \sigma_i^{F \mid t_i},  \sigma_i^{F \mid t_i} \leq \sigma_i^P  \right]  \\
    &=& \p{V_i > \sigma_i^{F \mid t_i} } \E{ \sigma_i^{F \mid t_i} \mid  V_i > \sigma_i^{F \mid t_i}, y \leq \sigma_i^{F \mid t_i} \leq \sigma_i^P  }  
    + \p{V_i \leq \sigma_i^{F \mid t_i} } \mathbb{E} \left[ \max\{y, V_i\}  \mid V_i \leq \sigma_i^{F \mid t_i} ,  y \leq \sigma_i^{F \mid t_i},  \sigma_i^{F \mid t_i} \leq \sigma_i^P  \right]  \\ 
    &=& \mathbb{E} \left[ \max \{ y, \min \{ V_i, \sigma_i^{F \mid t_i} \} \} \mid y \leq \sigma_i^{F \mid t_i},  \sigma_i^{F \mid t_i} \leq \sigma_i^P  \right] \ . 
\end{eqnarray*}
\end{small}

\end{enumerate}



\subsection{Optimal stopping}\label{apx:stopping}

We proceed to prove the optimal stopping rule in the general case. 
The overall proof strategy is to show that the stopping decision regarding a box (i.e., never open this box in the future) is independent of the existence of other boxes. 
Then, the optimal stopping rule shown in Section~\ref{sec:stopping} for the single box setting can be applied to the general case. 


We call a closed box $i$  ``F-expired'' if $y \geq \max \sigma_i^F$. 
We call a partially open box $i$ ``F-expired'' if $y \geq \sigma_i^{F \mid t_i}$. 
We call a closed box $i$ P-expired if $y \geq \sigma_i^P$. 
In what follows, we show that there exists an optimal policy that never F-opens an F-expired box and P-opens a P-expired box.

\paragraph{Case 1: F-expired box.}
First, we show that an optimal policy never F-opens an F-expired box. 
The proof proceeds by contradiction. 
Suppose that in state $(\mathcal{C}, \mathcal{P}, y)$ the optimal policy $\pi$ F-opens an F-expired box $i$. 
We define the information set $I_i$ of box $i$ to be $I_i \triangleq \emptyset$ if box $i$ is closed and $I_i \triangleq \{T_i=t_i \}$ if box $i$ is partially opened. 
By the Bellman equation, we have
$$
J^\pi(\mathcal{C}, \mathcal{P}, y) = -c_i^F + \mathbb{E}[J^\pi (\mathcal{C}', \mathcal{P}', \max\{y, V_i \} ) \mid I_i ],
$$
where $\mathcal{C}'=\mathcal{C}  \setminus \{i\}, P'=P$ if $i \in \mathcal{C}$ and $\mathcal{C}'=\mathcal{C}, \mathcal{P}'=\mathcal{P}\setminus \{i\}$ if $i \in \mathcal{P}$. 



We construct an alternative policy $\pi'$ that does not open box $i$; instead, it ``simulates'' a value for $V_i$, discards box $i$ for the remainder of the inspection process, and imitates the policy $\pi$ after that, with the only difference that $\pi'$ selects $y$ whenever policy $\pi$ selects box $i$. 
With this definition at hand, it is not difficult to show that the expected profit under policy $\pi'$ is given by
$$
J^{\pi'}(\mathcal{C}, \mathcal{P}, y) = \mathbb{E}\left[J^\pi (\mathcal{C}', \mathcal{P}', y  ) \mid I_i \right].
$$
The remainder of the proof proceeds by coupling the realizations of $V_i$ under the two policies to compare their expected profits. For any sample path $\rho$, we denote the realization of $V_i$ by $V_i^\rho$. Then, the difference in the value functions of the two policies is
\begin{eqnarray*}
 J_\rho^{\pi}(\mathcal{C}, \mathcal{P}, y) - J_\rho^{\pi'}(\mathcal{C}, \mathcal{P},y ) &=&  \left\{\begin{array}{ll}{ -c_i^F  } & { \text{if box i is not selected}} \\ {- c_i^F + \max \{y, V_i^\rho \} - y  }& { \text{ if box i is selected }}   \end{array}\right. \\
   &\leq& \left\{\begin{array}{ll}{ -c_i^F +  \max \{y, V_i^\rho \} - y  } & { \text{if box i is not selected}} \\ {- c_i^F + \max \{y, V_i^\rho \} - y }& { \text{ if box i is selected }}   \end{array}\right..
\end{eqnarray*}
Therefore, by taking expecations on both sides, we obtain 
$$
J^{\pi}(\mathcal{C}, \mathcal{P}, y ) - J^{\pi'}(\mathcal{C}, \mathcal{P}, y ) = \mathbb{E}_\rho \left[ J_\rho^{\pi}(\mathcal{C}, \mathcal{P}, y) - J_\rho^{\pi'}(\mathcal{C}, \mathcal{P},y ) \right] \leq \mathbb{E}\left[- c_i^F + \max \{y, V_i\} - y  \mid I_i\right] \ .
$$
Hence, other boxes do not affect the stopping decision regarding box $i$. 
Recalling the optimal stopping policy in the single box setting, one can easily verify that $\mathbb{E}\left[- c_i^F + \max \{y, V_i\} - y  \mid I_i\right] \leq 0 $ if box $i$ is F-expired.  
We conclude that there exists an optimal policy that does not F-open an F-expired box.

\paragraph{Case 2: P-expired box.}
Next, we prove that there exists an optimal policy that never P-opens a P-expired box. 
Suppose that in state $(\mathcal{C}, \mathcal{P}, y)$, the optimal policy $\pi$ P-opens a box $i$ with $y \geq \sigma_i^P $. 
We denote its value function by $J^\pi(\mathcal{C}, \mathcal{P}, y)$. Hence, we have 
$$
J^\pi(\mathcal{C}, \mathcal{P}, y) = -c_i^P + \mathbb{E}[J^\pi (\mathcal{C} \setminus \{i\}, \mathcal{P} \cup \{(i,T_i)\}, y ) ].
$$

Similar to Case 1, we construct an alternative policy $\pi'$ that ``simulates'' a type for $T_i$, discards box $i$ for the remainder of the inspection process, and imitates the policy $\pi$ after that, with the only difference that $\pi'$ selects $y$ whenever policy $\pi$ selects the box $i$. 
For any sample path $\rho$, we denote the realization of $T_i$ and $V_i$ by $t_i^\rho$ and $V_i^\rho$, respectively.
Then the difference between the expected profits of the two policies is
\begin{eqnarray}
& &  J_\rho^{\pi}(\mathcal{C}, \mathcal{P}, y) - J_\rho^{\pi'}(\mathcal{C}, \mathcal{P}, y) \nonumber \\ 
&=&
 \left\{\begin{array}{ll}
 { -c_i^P  } & { \text{if box i is not F-opened by }\pi} \\
 {-c_i^P - c_i^F   }& { \text{ if box i is F-opened, but not selected by } \pi }  \\
  {-c_i^P - c_i^F  + \max\{ V_i^\rho,y \}-y }              & { \text{ if box i is F-opened, and selected by } \pi  }
 \end{array}\right. \nonumber\\
   &\leq&
   \left\{\begin{array}{ll}
 { -c_i^P  } & { \text{if box i is not F-opened by }\pi} \\
 {-c_i^P - c_i^F  + \max\{ V_i^\rho,y \}-y    }& { \text{ if box i is F-opened, but not selected by } \pi }  \\
  {-c_i^P - c_i^F  + \max\{ V_i^\rho,y \}-y }              & { \text{ if box i is F-opened, and selected by } \pi  }
 \end{array}\right..   \label{eq:expired_box_sample_path_1}
\end{eqnarray}
We denote by $q_i^\pi(t_i^\rho) \in [0,1]$ the probability that policy $\pi$ F-opens box $i$ when the revealed type is $t_i^\rho$, and we define the set of  ``promising'' types  $\Lambda_i(y)=\{t_i \in \Gamma_i \mid y < \sigma_i^{F \mid t_i} \}$ which warrant F-opening. 

We next write an explicit expression for the expectation of the difference, splitting to cases based on \eqref{eq:expired_box_sample_path_1} and obtain the following:
\begin{eqnarray}
  J^{\pi}(\mathcal{C}, \mathcal{P},y ) - J^{\pi'}(\mathcal{C}, \mathcal{P},y )  &=&\mathbb{E}_\rho \left[J_\rho^{\pi}(\mathcal{C}, \mathcal{P}, y) - J_\rho^{\pi'}(\mathcal{C}, \mathcal{P}, y)    \right] \nonumber \\
   &\leq& -c_i^P + \sum_{t_i^\rho \in \Lambda_i(y)}\operatorname{Pr}[T_i=t_i^\rho]q_i^\pi(t_i^\rho) \left( \underbrace{-c_i^F + \mathbb{E}[(V_i-y)^+ \mid T_i=t_i^\rho]}_{>0}   \right)  \nonumber  \\
   & & + \left(\sum_{t_i^\rho \notin \Lambda_i(y)}\operatorname{Pr}[T_i=t_i^\rho]+\sum_{t_i^\rho \in \Lambda_i(y)}\operatorname{Pr}[T_i=t_i^\rho]\left(1-q_i^\pi(t_i^\rho)\right) \right) \cdot 0    \label{eq:expired_box_sample_path_2}  \\
   &\leq& -c_i^P + \sum_{t_i^\rho \in \Lambda_i(y)}\operatorname{Pr}[T_i=t_i^\rho] \left( \underbrace{-c_i^F + \mathbb{E}[(V_i-y)^+ \mid T_i=t_i^\rho]}_{>0}   \right) \label{eq:expired_box_sample_path_3} \ . 
   % &=& \Delta_i^P(\mathcal{C}, \mathcal{P}, y) \leq 0  \nonumber.
\end{eqnarray}
Inequality \eqref{eq:expired_box_sample_path_2} is based on \eqref{eq:expired_box_sample_path_1}, multiplied by the conditional probability of type $T_i$.


We showed that there exists an optimal policy that stops when all boxes F-expire and P-expire. On the other hand, if there is even a single box that did not F-expire or P-expire, opening such box is better than stopping. The latter follows from the the single-box case. Therefore, the stopping condition is both sufficient and necessary.






\subsection{Proof of Theorem~\ref{thm:just_strong}}
\label{appendix:thm_just_strong}

The proof consists of two parts, dealing with cases where the box that attains the largest F-opening threshold is either partially open or closed. We prove these cases as separate lemmas.

\begin{lemma} \label{lemma:just_strong_partial}
For every state $(\mathcal{C}, \mathcal{P}, y)$ where it is suboptimal to stop,  if the F-threshold of a partially opened box $k$ is the largest opening threshold among boxes in that state, then there exists an optimal policy that F-opens box $k$ at that state.
\end{lemma}

\begin{myproof}
The lemma applies to cases in which there is at least one partially opened box, implying $\mid\mathcal{P}\mid \geq 1$. We prove the lemma by induction on the maximal potential number of box openings from a given state, which is captured by the expression:  $2\mid\mathcal{C}\mid + \mid\mathcal{P}\mid$ (each partially opened box can be opened at most once, while closed boxes can be opened at most twice, first being P-opened and then F-opened). We denote by $k$ the index of the partially open box whose F-threshold is the largest opening threshold in state $(\mathcal{C}, \mathcal{P}, y)$. With a slight abuse of notation, we denote by $\sigma_k$  the conditional F-threshold of box $k$:
$$
\sigma_k 
\triangleq 
\sigma_k^{F \mid t_k} = \sigma_M\left(\mathcal{C},\mathcal{P} \right).
$$
Since stopping is assumed to be sub-optimal, the optimal stopping condition implies that $y< \sigma_k$.

As base cases, consider states where $2  \mid \mathcal{C} \mid + \mid \mathcal{P} \mid  \in \{1,2\}$. Since $\mid\mathcal{P}\mid \geq 1$, this implies that $\mid\mathcal{C}\mid=0$. We observe that whenever $\mid\mathcal{C}\mid=0$ the problem reduces to the standard Pandora's box problem, from which the optimality of the lemma follows. 




For the induction step, suppose that the lemma holds in states where $2  \mid \mathcal{C} \mid + \mid \mathcal{P} \mid  =  3,\ldots,n $, where $n\geq 3$. We will show that the property still holds when $2  \mid \mathcal{C} \mid + \mid \mathcal{P} \mid  =  n + 1$.
Assume by contradiction that at a state $(\mathcal{C}, \mathcal{P}, y)$ where $2  \mid \mathcal{C} \mid + \mid \mathcal{P} \mid  =  n + 1$ any  optimal policy does not F-open box $k$. We will construct an alternative policy $\pi'$ that does F-open box $k$ at that state and which performs at least as well as policy $\pi$.
Since stopping is suboptimal in state $(\mathcal{C}, \mathcal{P}, y)$, there are two possibilities for the next action under policy $\pi$; it either F-opens or P-opens another box.




\paragraph{Case~1: Policy $\pi$ F-opens a box $i\neq k$.} 

Suppose first that policy $\pi$  F-opens a box $i \in \mathcal{C}$. Then the system transitions to a state $(\mathcal{C}', \mathcal{P}', y')$ where $2  \mid \mathcal{C} ' \mid  + \mid \mathcal{P}' \mid  = n-1$. 
From Theorem~\ref{thm:myopic_stopping}, in the next state it is optimal to stop if $V_i > \sigma_k$, since $\sigma_k$ remains the largest threshold. Therefore, if $V_i > \sigma_k$, policy $\pi$ stops, otherwise, using the induction hypothesis, we know that policy $\pi$ will F-open box $k$ and stop afterward if $V_k > \sigma_k$. 
Defining $p_s = \operatorname{Pr} \Big[V_s > \sigma_k \Big]$ for each box $s \in \{i,k\}$, we can write the expected profit under policy $\pi$ as
\begin{eqnarray*}
  J^{\pi}(\mathcal{C}, \mathcal{P}, y) &=& - c_i^F + p_i \cdot \mathbb{E}\left[V_i \mid V_i > \sigma_k\right]  \\
   &+&   (1-p_i) \cdot \Big( -c_k^F +   p_k \cdot \mathbb{E}\left[V_k \mid V_k > \sigma_k\right] \\ 
   && +  (1-p_k) \cdot \mathbb{E} \left[   J^{\pi}(\mathcal{C}', \mathcal{P}', \max \left \{y, V_k, V_i \right \}  ) \mid   V_k \leq \sigma_k, V_i \leq \sigma_k \right] \Big),
\end{eqnarray*}
where $\mathcal{C}' = \mathcal{C} \setminus \{ i\} $ and $\mathcal{P}' = \mathcal{P} \setminus \{ k \}$.  


We construct an alternative policy $\pi'$ that first F-opens box $k$ and selects box $k$ if $V_k > \sigma_k$; otherwise, policy $\pi'$ F-opens box $i$, and proceeds to  selecting box $i$ if $V_i > \sigma_k$. In the event that $V_i \leq \sigma_k$ (and $V_k \leq \sigma_k$), policy $\pi'$ imitates  policy $\pi$ thereafter. Therefore, the expected profit of policy $\pi'$ is
\begin{eqnarray*}
  J^{\pi'}(\mathcal{C}, \mathcal{P}, y) &=& - c_k^F + p_k  \cdot \mathbb{E}\left[V_k \mid V_k > \sigma_k\right]  \\
   &+&   (1-p_k) \cdot \Big( -c_i^F +   p_i \cdot \mathbb{E}\left[V_i \mid V_i > \sigma_k\right] \\ 
   && + (1-p_i) \cdot \mathbb{E} \left[    J^{\pi}(\mathcal{C}', \mathcal{P}', \max\{y, V_k, V_i \}  ) \mid  V_k \leq \sigma_k, V_i \leq \sigma_k \right] \Big).
\end{eqnarray*}
Using simple arithmetics, we can write the difference between $ J^{\pi}(\mathcal{C}, \mathcal{P}, y) $ and $ J^{\pi'}(\mathcal{C}, \mathcal{P}, y) $ as follows: 
\begin{eqnarray}
  J^{\pi'}(\mathcal{C}, \mathcal{P}, y) -J^{\pi}(\mathcal{C}, \mathcal{P}, y) &=& - c_k^F + p_k \cdot \mathbb{E}\left[V_k \mid V_k > \sigma_k\right] + (1-p_k) \cdot \left(   -c_i^F +   p_i \cdot \mathbb{E}\left[V_i \mid V_i > \sigma_k\right] \right) \nonumber \\
   & &  +  c_i^F  - p_i \cdot \mathbb{E}\left[V_i \mid V_i > \sigma_k\right] - (1-p_i) \cdot \left(   -c_k^F +   p_k \cdot \mathbb{E}\left[V_k \mid V_k > \sigma_k\right] \right)  \nonumber \\
   &=& p_k p_i \cdot \left( \mathbb{E}\left[V_k \mid V_k > \sigma_k\right] - \mathbb{E}\left[V_i \mid V_i > \sigma_k\right] \right)  + p_k c_i^F - p_i c_k^F \nonumber \\
   &=& p_k p_i \cdot \left( \mathbb{E}\left[V_k -\sigma_k \mid V_k > \sigma_k\right] - \mathbb{E}\left[V_i -\sigma_k  \mid V_i > \sigma_k\right] \right)  + p_k c_i^F - p_i c_k^F \nonumber \\
   &=& p_i \cdot \mathbb{E}\left[(V_k -\sigma_k )^+\right] - p_k \cdot \mathbb{E}\left[(V_i -\sigma_k )^+\right] + p_k c_i^F - p_i c_k^F   \nonumber \\
   &=& p_i c_k^F  - p_k \cdot \mathbb{E}\left[(V_i -\sigma_k )^+\right] + p_k c_i^F - p_i c_k^F \nonumber \\
   &=& - p_k \cdot \mathbb{E}\left[(V_i -\sigma_k )^+\right] + p_k \cdot \mathbb{E} \left[(V_i -\sigma_i^F )^+\right] \nonumber .
   %&\geq& 0 ~~~ \text{ (whenever } \sigma_k > \sigma_i^F \text{ )} . \label{eq:thm_just_strong_interchange_1}    \nonumber
\end{eqnarray}
The latter is nonnegative whenever $\sigma_k \geq \sigma_i^F$, which is the case considered in the lemma. Therefore,  policy $\pi'$ achieves at least the same expected profit as policy $\pi$, which concludes the proof of this case. % , which contradicts the optimality of the latter policy. 


We briefly note that the case in which policy $\pi$ F-opens a box $i \in \mathcal{P}$ can be proved similarly and, for brevity, is omitted. 



\paragraph{Case~2: Policy $\pi$ starts by P-opening a box $i \in \mathcal{C}$.}
Suppose policy $\pi$ P-opens a box $i \in \mathcal{C}$. Then the system transitions to a state $(\mathcal{C}', \mathcal{P}', y)$ for which $2  \mid \mathcal{C} ' \mid  + \mid \mathcal{P}' \mid  = n$. By our induction hypothesis, after this P-opening action, if the revealed type $t_i$ is such that $\sigma_i^{F \mid t_i} > \sigma_k$, policy $\pi$ will immediately F-open box $i$. Consequently,  by the induction hypothesis, after box $i$ is F-opened, if it is suboptimal to stop, policy $\pi$ will then F-open box $k$.
Otherwise, if the revealed type $t_i$ is such that $\sigma_i^{F \mid t_i} \leq \sigma_k$, then, by the induction hypothesis, policy  $\pi$ will F-open box $k$. Policy $\pi$ is illustrated Figure~\ref{diag:just_strong_interchange_1}.
The expected profit of policy $\pi$ is
          \begin{eqnarray}
            J^{\pi}(\mathcal{C}, \mathcal{P}, y) &=& -c_{i}^{p}+ \operatorname{Pr} \left[ \sigma_{i}^{F \mid  T_{i}}>\sigma_{k}\right] \bigg( -c_{i}^{F} + \operatorname{Pr} \left[  V_{i} > \sigma_{k} \middle\vert \sigma_{i}^{F \mid  T_{i}}>\sigma_{k} \right] \mathbb{E} \left[  V_{i} \mid V_{i}>\sigma_{k}, \sigma_{i}^{F  \mid  T_{i}} > \sigma_{k}\right]  \nonumber \\
             &+&    \operatorname{Pr}\left[   V_{i} \leq \sigma_{k} ~\middle \vert~  \sigma_{i}^{F \mid  T_{i}} > \sigma_{k} \right] \left( -c_{k}^{F}+ \operatorname{Pr} \left[V_{k}>\sigma_{k}\right] \cdot \mathbb{E}\left[V_{k} \mid V_{k}>\sigma_{k}\right]
             + \operatorname{Pr}\left[V_{k} \leq  \sigma_{k}\right] \cdot J_1  \right) \bigg) \nonumber  \\
             &+&  \operatorname{Pr} \left[\sigma_{i}^{F \mid  T_i} \leq  \sigma_{k}\right] \Big( -c_{k}^{F}+\operatorname{Pr}\left[V_{k}>\sigma_{k}\right]  \mathbb{E}\left[V_{k} \mid V_{k}>\sigma_{k}\right]+ \operatorname{Pr}\left[V_{k} \leq \sigma_{k}\right] \cdot J_2 \Big),  \nonumber
          \end{eqnarray}
          where $ J_1 = \mathbb{E} \left[ J^{\pi} \left( \mathcal{C} \setminus \{ i \}, \mathcal{P} \setminus \{ k \}, \max\{ y, V_i, V_k\} \right) ~\middle \vert~ \sigma_{i}^{F \mid  T_{i}}>\sigma_{k}, V_i \leq \sigma_k, V_k \leq \sigma_k \right] $, and  \\
          $ J_2 = \mathbb{E} \left[ J^{\pi}\left( \mathcal{C} \setminus \{ i \}, \mathcal{P} \setminus \{ k \} \cup \{i \}, \max\{ y,  V_k\} \right) ~\middle \vert~ \sigma_{i}^{F \mid  T_{i}} \leq \sigma_{k}, V_k \leq \sigma_k \right] $.

\begin{figure}[htbp]
\centering
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=0.95\linewidth]{graphs/just_strong_interchange_policy_pi.png}
    \caption{Policy $\pi$}
   \label{diag:just_strong_interchange_1}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=0.8\linewidth]{graphs/just_strong_interchange_policy_pi_prime.png}
  \caption{Policy $\pi'$}
  \label{diag:just_strong_interchange_2}
\end{subfigure}
\caption{ A graphical illustration of policy $\pi$ and policy $\pi'$ for Case 2, in the Proof of Lemma~\ref{lemma:just_strong_partial}.   }
\label{fig:just_strong_interchange_policy}
\end{figure}

Similarly to Case 1, we construct an alternative policy $\pi'$ that first F-opens box $k$, as shown in Figure~\ref{diag:just_strong_interchange_2}. If $V_k \leq \sigma_k$, policy $\pi'$  proceeds to P-opening box $i$, and it then F-opens box $i$ if the type $T_i$ is such that $\sigma_i^{F \mid T_i} > \sigma_k$.
Otherwise, $\pi'$ imitates policy $\pi$ in all subsequent states. 
Therefore, the expected profit of policy $\pi'$ can be written as follows: 
\begin{eqnarray}
& & J^{\pi'}(\mathcal{C}, \mathcal{P}, y)  \nonumber \\
 &=&  -c_{k}^{F} + \operatorname{Pr}\left[V_{k} > \sigma_{k}\right] \mathbb{E}\left[V_{k} \mid V_{k} > \sigma_{k}\right] \nonumber \\
 &+& \operatorname{Pr}\left[V_{k} \leq  \sigma_{k}\right] \bigg(  - c_i^P + \operatorname{Pr} \left[\sigma_{i}^{F \mid  T_{i}}>\sigma_{k}\right]  \Big(  -c_i^F + \operatorname{Pr}\left[ V_{i}>\sigma_{k} ~\middle \vert~ \sigma_{i}^{F \mid  T_{i}}>\sigma_{k} \right] \mathbb{E} \left[ V_i ~\middle \vert~ V_i > \sigma_k,  \sigma_{i}^{F \mid  T_{i}}>\sigma_{k}  \right] \nonumber \\
 &+& \operatorname{Pr}\left[V_{i} \leq \sigma_{k} ~\middle \vert~ \sigma_{i}^{F \mid  T_{i}}>\sigma_{k} \right] \cdot J_1 \Big) + \operatorname{Pr}\left[ \sigma_{i}^{F \mid  T_{i}} \leq \sigma_{k} \right] \cdot  J_2 \bigg).   \nonumber
\end{eqnarray}

Let $p_k = \operatorname{Pr}\left[V_{k}>\sigma_{k}\right]$, $q_i = \operatorname{Pr} \left[\sigma_{i}^{F \mid  T_{i}}>\sigma_{k}\right]$, and $p_i = \operatorname{Pr} \left[V_i > \sigma_k \mid \sigma_{i}^{F \mid  T_{i}}>\sigma_{k}\right]$. The difference between $ J^{\pi}(\mathcal{C}, \mathcal{P}, y) $ and $ J^{\pi'}(\mathcal{C}, \mathcal{P}, y) $ can be written as 
\begin{eqnarray}
& & J^{\pi'}(\mathcal{C}, \mathcal{P}, y) - J^{\pi}(\mathcal{C}, \mathcal{P}, y) \nonumber  \\
&=& \left( -c_k^F + q_i(1-p_i) c_k^F + (1-q_i) c_k^F \right) + \left( -(1-p_k)c_i^P + c_i^P \right)  + \left( -(1-p_k)q_ic_i^F + q_i c_i^F \right)  \nonumber \\
 & & +  p_k q_i p_i \cdot \mathbb{E}\left[V_{k} \mid V_{k}>\sigma_{k}\right]  -   p_k q_i p_i \cdot \mathbb{E} \left[  V_i ~ \middle \vert~    V_i > \sigma_k,  \sigma_{i}^{F \mid  T_{i}}>\sigma_{k}  \right]      \nonumber  \\
 &=& -q_i p_i c_k^F + p_k c_i^P + p_k q_i c_i^F   \nonumber  \\
 & & +  p_k q_i p_i \cdot \left( \mathbb{E}\left[V_{k} \mid V_{k}>\sigma_{k}\right]-\sigma_k \right)  -   p_k q_i p_i  \cdot \left( \mathbb{E} \left[ V_i ~\middle \vert~ V_i > \sigma_k,  \sigma_{i}^{F \mid  T_{i}}>\sigma_{k}  \right] -\sigma_k \right) \nonumber  \\
 &=& -q_i p_i c_k^F + p_k c_i^P + p_k q_i c_i^F   \nonumber  \\
 & & +   q_i p_i  \cdot \mathbb{E}\left[ \left( V_{k}  -\sigma_k  \right)^+\right]  -   p_k q_i \cdot \mathbb{E} \left[ \left( V_i - \sigma_k \right)^+ ~\middle \vert~ \sigma_{i}^{F \mid  T_{i}}>\sigma_{k}  \right]   \nonumber \\
 &=&  p_k \cdot \left(  c_i^P + q_i c_i^F    -   q_i \cdot \mathbb{E} \left[ \left( V_i - \sigma_k \right)^+ ~\middle \vert~ \sigma_{i}^{F \mid  T_{i}}>\sigma_{k}  \right] \right) \nonumber \\
 &=&  p_k \cdot \left(  c_i^P -  \operatorname{Pr} \left[\sigma_{i}^{F \mid  T_{i}}>\sigma_{k}\right] \left( - c_i^F    +    \mathbb{E} \left[ \left( V_i - \sigma_k \right)^+ ~\middle \vert~ \sigma_{i}^{F \mid  T_{i}}>\sigma_{k}  \right] \right) \right)  \nonumber   \\
 &=&  p_k \cdot \left(  \mathbb{E}\left[ \max \left\{0, -c_i^F + \mathbb{E}\left[ (V_i - \sigma_i^P )^+\right] \right\} \right] -  \mathbb{E}\left[ \max \left \{0, -c_i^F + \mathbb{E}\left[ (V_i - \sigma_k )^+\right] \right \} \right] \right)  \nonumber .
\end{eqnarray}
The latter is nonnegative whenever $\sigma_k \geq \sigma_i^P$, which is the case considered in the lemma. 
This shows that policy $\pi'$ achieves at least the same expected profit as policy $\pi$, thereby concluding the proof of Case 2 and the lemma.
\end{myproof}


We next turn to the second part of the theorem. To this end, we first make a notable observation. 

\begin{restatable}[]{lemma}{Pdominated} \label{lemma:P_dominated}
For a closed box $i \in \mathcal{C}$, P-opening is dominated if $\sigma_i^F > \sigma_i^P$.
\end{restatable}

Given this claim, it is straightforward to establish the second part of Theorem~\ref{thm:just_strong}. 
\begin{lemma} \label{lemma:just_strong_closed}
For every state $(\mathcal{C}, \mathcal{P}, y)$ such that it is suboptimal to stop,  if the F-threshold of a closed box $i$ with $\sigma_i^F > \sigma_i^P$ is the largest  opening threshold, then there exists an optimal policy that F-opens box $i$ immediately. 
\end{lemma}


\begin{myproof2}{Lemma \ref{lemma:just_strong_closed}}
According to Lemma~\ref{lemma:P_dominated}, P-opening box $i$ is a dominated action. 
Therefore, we can view box $i$ as a partially opened box that can only be F-opened. From Lemma~\ref{lemma:just_strong_partial} and the fact that $\sigma_i^F$ is the leading threshold, it follows that an optimal policy exists that F-opens box $i$ immediately.  % \Halmos
\end{myproof2}




\begin{myproof2}{Lemma \ref{lemma:P_dominated}}

Let $m$ be the index of the box with the largest opening threshold excluding box $i$, and let $\sigma_m$ be its opening threshold. i.e.,
$$
\sigma_m =  \max \left\{  \underset{j \in \mathcal{C} \setminus \{ i\}}{\max}  \left\{  \sigma_j^F, \sigma_j^P \right\}, \underset{ j \in \mathcal{P}}{\max }  \left\{ \sigma_j^{F \mid t_j}  \right\}   \right\}.
$$

If $y > \sigma_m$, then boxes other than box $i$ should not be opened (such boxes F-expire and P-expire, see the proof of Theorem~\ref{thm:myopic_stopping}), and the problem reduces to the single box case for which Theorem~\ref{thm:just_strong} is a direct consequence of Theorem~\ref{thm:myopic_stopping}. As such, in what follows, we consider the case where $y \leq \sigma_m$.

Suppose an optimal policy $\pi$ P-opens the box $i$ in state $(\mathcal{C}, \mathcal{P}, y)$. 
We will construct an alternative policy $\pi'$ that F-opens box $i$ instead at that state, and show that it achieves an expected profit  at least as high as that of policy $\pi$. 
According to Lemma \ref{lemma:just_strong_partial}, after P-opening box $i$, policy $\pi$ proceeds to F-opening box $i$ if $\sigma_i^{F \mid T_i} > \sigma_m $, and it will then stop if $V_i > \sigma_m$. 
  We denote by $G_i$ the set of types associated with box $i$ in which policy $\pi$ is guaranteed to F-open box $i$ immediately upon P-opening, i.e.,  $T_i \in G_i \Leftrightarrow \sigma_i^{F \mid T_i} > \sigma_m $. 



  Therefore, the expected profit of policy $\pi$ is
  \begin{eqnarray}
    J^{\pi}(\mathcal{C}, \mathcal{P}, y) &=&  -c_i^P + \operatorname{Pr} \left[ T_i \in G_i  \right] \bigg( -c_i^F + \operatorname{Pr} \left[ V_i > \sigma_m \mid T_i \in G_i  \right] \mathbb{E}\left[ V_i \mid V_i > \sigma_m, T_i \in G_i   \right]    \nonumber  \\
     & & +  \operatorname{Pr} \left[ V_i \leq \sigma_m \mid T_i \in G_i  \right] \cdot J_1   \bigg)   +  \operatorname{Pr} \left[ T_i \notin G_i   \right] \cdot  J_2, 
    \label{eq:lemma:P_dominated_J}
  \end{eqnarray}
  where $J_1 = \mathbb{E} \left[  J^{\pi}(\mathcal{C} \setminus \{ i \} , \mathcal{P}, \max \{y, V_i  \} )  \mid V_i \leq \sigma_m , T_i \in G_i \right]$ and $J_2 = \mathbb{E}\left[ J^{\pi}(\mathcal{C} \setminus \{ i \} , \mathcal{P} \cup \{i, t_i \}, y )  \mid T_i \notin G_i  \right]$.

\begin{figure}
  \centering
  \includegraphics[width=10cm]{graphs/policy_align_just_strong_closed.png}
  \caption{Illustration of payoffs of two policies in different scenarios. The y-axis denotes the realization of the prize, and the x-axis denotes the realization of the conditional threshold.}
  \label{fig:policy_align_just_strong_closed}
\end{figure}

\paragraph{Constructing an alternative policy $\pi'$.}
Let $\pi'$ be the policy that F-opens box $i$ in state $(\mathcal{C}, \mathcal{P}, y)$, and selects box $i$ if $V_i > \sigma_m$; otherwise, it further imitates policy $\pi$ with the only difference that, whenever policy $\pi$ F-opens box $i$, policy $\pi'$ who already observed the value of box $i$, does nothing and no longer incurs the cost $c_i^F$. Therefore, the expected profit of policy $\pi'$ is given by
  \begin{eqnarray}
    J^{\pi'}(\mathcal{C}, \mathcal{P}, y) &=&  -c_i^F + \operatorname{Pr} \left[ T_i \in G_i  \right]  \operatorname{Pr} \left[ V_i > \sigma_m \mid T_i \in G_i  \right] \mathbb{E}\left[ V_i \mid V_i > \sigma_m, T_i \in G_i   \right]  \nonumber  \\
    &+&    \operatorname{Pr} \left[ T_i \notin G_i  \right]  \operatorname{Pr} \left[ V_i > \sigma_m \mid T_i \notin G_i  \right] \mathbb{E}\left[ V_i \mid V_i > \sigma_m, T_i \notin G_i   \right]              \nonumber    \\
    &+& \operatorname{Pr} \left[ T_i \in G_i  \right]  \operatorname{Pr} \left[ V_i \leq \sigma_m \mid T_i \in G_i  \right] \cdot  J_1            \nonumber      \\
    &+& \operatorname{Pr} \left[ T_i \notin G_i  \right]  \operatorname{Pr} \left[ V_i \leq \sigma_m \mid T_i \notin G_i  \right]\cdot J_2', \label{eq:lemma:P_dominated_J'}  % \Big[ E + \theta_i^{\pi}  \cdot J_3 \Big].
  \end{eqnarray}
  where $J_2' =  \mathbb{E}\left[ J^{\pi'}(\mathcal{C} \setminus \{ i \} , \mathcal{P} , \max\{ y, V_i\} )  \mid V_i \leq \sigma_m ,  T_i \notin G_i  \right]$, which is the expected profit of policy $\pi'$ starting with the imitation of policy $\pi$, after observing that  $T_i \notin G_i$ and $V_i \leq \sigma_m $. 
  

  In what follows, we argue that $J^{\pi'}(\mathcal{C}, \mathcal{P}, y) \geq J^{\pi}(\mathcal{C}, \mathcal{P}, y)$. 
  The argument is established by first decomposing $J_2$ and $J_2'$ in a way that facilitates the comparison between $J^{\pi}$ and $J^{\pi'}$. 
  
  


\paragraph{Decomposition of $J_2$ and $J_2'$.}
   In order to compare the expected profits $J^{\pi}$ and $J^{\pi'}$, we decompose the terms $J_2$ and $J_2'$ appearing in equations~\eqref{eq:lemma:P_dominated_J} and~\eqref{eq:lemma:P_dominated_J'}, respectively. For this purpose, we can think of a policy as a decision tree consisting of nodes and edges. Each node represents a state-action pair and each edge captures a transition.  We call the nodes where the policy does not stop and opens a box \textit{interior} nodes, and the nodes where the policy stops are called \textit{terminal} nodes. Let $\text{box}(\tau)$ be the box that the policy  selects at a terminal node $\tau$. Let $c(\eta)$ be the opening cost paid at an interior node $\eta$.  Then, we have
  \begin{eqnarray}
    J_2 &=& \sum_{\text{terminal node } \tau   } \operatorname{Pr}\left[ \pi \text{ reaches } \tau \mid T_i \notin G_i \right] \cdot \mathbb{E} \left[ V_{\text{box}(\tau)} \mid \text{info regarding } \text{box}(\tau) \right]   \nonumber \\
     &-& \sum_{\text{interior node } \eta   }  \operatorname{Pr}\left[ \pi \text{ reaches } \eta \mid T_i \notin G_i \right] \cdot c(\eta) \nonumber .
  \end{eqnarray}
  For simplicity, we assume that there is only one node in the decision tree of policy $\pi$ that  F-opens box $i$ when $T_i \notin G_i $. By a slight abuse of language, we refer to this state-action pair as node $i$. 
  If there are multiple such nodes, the same reasoning applies. 
  Let $tree(i)$ be the subtree rooted at the node $i$. Then, on all paths outside $tree(i)$, policy $\pi$ does not F-open box $i$.
  According to Lemma~\ref{lemma:just_strong_partial}, if a conditional threshold greater than $\sigma_m$ is revealed by a P-opening inspection, the corresponding box is immediately F-opened in an optimal policy.
  Therefore, when node $i$ is reached, box $i$ will be F-opened, and it will be selected if $V_i > \sigma_m$. 
  We let $\theta_i^\pi = \operatorname{Pr}\left[ \pi \text{ reaches node } i \mid T_i \notin G_i \right]$. Based on the preceding discussion, $J_2$ can be expressed as
   \begin{eqnarray}
    J_2 &=& E + \theta_i^\pi  \cdot \Big( -c_i^F +   \operatorname{Pr} \left[ V_i > \sigma_m  \mid T_i \notin G_i  \right]   \mathbb{E}\left[ V_i \mid V_i > \sigma_m, T_i \notin G_i   \right]     + \operatorname{Pr} \left[ V_i \leq \sigma_m  \mid T_i \notin G_i  \right]  \cdot J_3  \Big),  \nonumber
  \end{eqnarray}
where we denote, for brevity, 
\begin{eqnarray}
 E &\triangleq& \sum_{ \substack{ \text{terminal node } \tau \\ \text{ outside } tree(i) }    } \operatorname{Pr}\left[ \pi \text{ reaches } \tau \mid T_i \notin G_i \right] \cdot \mathbb{E} \left[ V_{\text{box}(\tau)} \mid \text{info regarding } \text{box}(\tau) \right]  \nonumber \\
     &-& \sum_{\substack{ \text{interior node } \eta \\ \text{ outside } tree(i) }    }  \operatorname{Pr}\left[ \pi \text{ reaches } \eta \mid T_i \notin G_i \right] \cdot c(\eta)  .       \nonumber
\end{eqnarray}
We now turn our attention to the decomposition of $J_2'$. Let $J_3$ be the expected profit conditional on $T_i \notin G_i$ over all the sample paths that reach node $i$ in the decision tree associated with policy $\pi$.
After F-opening box $i$, policy $\pi'$ generates the same total profit as policy $\pi$ if node $i$ is not reached. 
If node $i$ is reached, policy $\pi'$ does not need to pay an additional cost for inspection. Since policy $\pi'$ has already observed that $T_i \notin G_i$ and $ V_i \leq \sigma_m $, we obtain $J_2' = E +  \theta_i^\pi  \cdot J_3$. In the next claim, we provide an upper bound on $E$ using the above decision-tree decomposition of costs. The proof appears at the end of this section.



\begin{figure}
  \centering
  \includegraphics[width=12cm]{graphs/tree.png}
  \caption{Illustration of $J_2$ via decision-tree-based coupling.}
  \label{fig:tree}
\end{figure}
  
  
\begin{claim}\label{lemma:E_bound} $E \leq  \left( 1- \theta_i^{\pi} \right) \cdot \sigma_m$ .    
\end{claim}





\paragraph{Bounding the difference between $J^{\pi'}$ and $J^{\pi}$.} Following the preceding discussion, we have 
\begin{eqnarray}
    & & J^{\pi'}(\mathcal{C}, \mathcal{P}, y) -  J^{\pi}(\mathcal{C}, \mathcal{P}, y) \nonumber \\
     &=& c_i^P + \operatorname{Pr} \left[ T_i \notin G_i  \right] \bigg( - \left(1- \theta_i^{\pi} \right) c_i^F  +  \left(1- \theta_i^{\pi} \right) \operatorname{Pr} \left[ V_i > \sigma_m \mid T_i \notin G_i  \right]  \mathbb{E}\left[ V_i \mid V_i > \sigma_m, T_i \notin G_i   \right]  \nonumber  \\
     & & -  \operatorname{Pr} \left[ V_i > \sigma_m \mid T_i \notin G_i  \right] \cdot E    \bigg)  \nonumber \\
     &\geq&    c_i^P + \operatorname{Pr} \left[ T_i \notin G_i  \right] \bigg( - \left(1- \theta_i^{\pi} \right) c_i^F  +  \left(1- \theta_i^{\pi} \right) \operatorname{Pr} \left[ V_i > \sigma_m \mid T_i \notin G_i  \right]  \mathbb{E}\left[ V_i \mid V_i > \sigma_m, T_i \notin G_i   \right]   \nonumber \\
     & &  -  \operatorname{Pr} \left[ V_i > \sigma_m \mid T_i \notin G_i  \right] \cdot \left(1- \theta_i^{\pi} \right) \sigma_m   \bigg)   \label{eq:thm_just_strong_closed_diff_1}
\end{eqnarray}
\begin{eqnarray}
     &=&  c_i^P +  \left(1- \theta_i^{\pi} \right)  \operatorname{Pr} \left[ T_i \notin G_i  \right] \bigg( - c_i^F  +   \operatorname{Pr} \left[ V_i > \sigma_m \mid T_i \notin G_i  \right] \left( \mathbb{E}\left[ V_i \mid V_i > \sigma_m, T_i \notin G_i   \right] - \sigma_m  \right) \bigg)   \nonumber \\
     &=&   c_i^P +  \left(1- \theta_i^{\pi} \right)  \operatorname{Pr} \left[ T_i \notin G_i  \right] \bigg( \underbrace{ - c_i^F  +  \mathbb{E} \left[ (V_i - \sigma_m )^+ \mid T_i \notin G_i \right]}_{\leq 0 \text{ since } \sigma_m \geq \sigma_i^{F \mid T_i}  \text{ for } T_i \notin G_i  } \bigg) \nonumber \\
     &\geq& c_i^P +  \operatorname{Pr} \left[ T_i \notin G_i  \right] \bigg(  - c_i^F  +  \mathbb{E} \left[ (V_i - \sigma_m )^+ \mid T_i \notin G_i \right]  \bigg) \nonumber \\
     &\geq& 0 \ .  \label{eq:to_explain} %  \Delta_i^{F,P}(\sigma_m) \geq 0  .
\end{eqnarray}
Equation~\eqref{eq:thm_just_strong_closed_diff_1} follows from Lemma~\ref{lemma:E_bound}.
The last inequality proceeds in the same reasoning as \eqref{eq:lemma:monotonicity_myopic_gain_SW} in the single-box setting, by noting that $ \left\{  T_i \notin G_i \right\} \Leftrightarrow  \left\{  T_i \notin \Lambda_i ( \sigma_m) \right\} $ and $\sigma_i^{F/P} > \sigma_m$. 



To complete the proof of Theorem~\ref{thm:just_strong}, it remains to establish Claim~\ref{lemma:E_bound}.

\begin{myproof2}{Claim \ref{lemma:E_bound}}


We decompose the expected cumulative costs $E$ into three types of nodes (inspections or selections) in the decision-tree: (i) F-opening a box at an interior node, then selecting its reward when it is greater than $\sigma_m$; (ii) $P$-opening a box at an interior node, then $F$-opening it and selecting the reward when the conditional threshold and reward are greater than $\sigma_m$, respectively; and (iii) selecting a box at a terminal node with reward smaller or equal to $\sigma_m$. These three types partition all the nodes of the decision tree. Indeed, (i) when $\sigma_m$ is greater than all remaining thresholds, by Theorem \ref{thm:myopic_stopping}, it is optimal to select a box if its prize is found to be greater than $\sigma_m$; (ii) when a conditional threshold greater than $\sigma_m$ is found, the optimal policy immediately F-opens it by Lemma \ref{lemma:just_strong_partial}; and (iii) in all other cases, the prize value is bounded by $\sigma_m$.
Consequently, we obtain the following expression:
\begin{eqnarray}
  E &=& \sum_{\substack{ \text{interior node } \eta \\ \text{ outside } tree(i)   \\ \text{action} (\eta)= \text{F-open}  \\ \sigma_{\text{box}(\eta)} \leq \sigma_m  }    }  \operatorname{Pr} \left[ \pi \text{ reaches } \eta \mid T_i \notin G_i \right] \Bigg( - c_{\text{box}(\eta)}^{F} +  \operatorname{Pr} \left[ V_{\text{box}(\eta) } > \sigma_m \right] \mathbb{E} \left[ V_{\text{box}(\eta)} \mid V_{\text{box}(\eta)} > \sigma_m \right]  \Bigg)  \nonumber    \\
  &+& \sum_{\substack{ \text{interior node } \eta \\ \text{ outside } tree(i)   \\ \text{action} (\eta)= \text{P-open} }}  \operatorname{Pr} \left[ \pi \text{ reaches } \eta \mid T_i \notin G_i \right]  \Bigg(  - c_{\text{box}(\eta)}^P + \operatorname{Pr} \left[ \sigma_{\text{box}(\eta)}^{F \mid t_{\text{box}(\eta)}} > \sigma_m   \right] \nonumber  \\
  & & \cdot \bigg(  -c_{\text{box}(\eta)}^F + 
  \operatorname{Pr} \left[  V_{\text{box}(\eta)} > \sigma_m ~\middle \vert~ \sigma_{\text{box}(\eta)}^{F \mid t_{\text{box}(\eta)}} > \sigma_m  \right]  
  \mathbb{E} \left[  V_{\text{box}(\eta)} ~\middle \vert~ V_{\text{box}(\eta)} > \sigma_m ,  \sigma_{\text{box}(\eta)}^{F \mid t_{\text{box}(\eta)}} > \sigma_m  \right] \bigg) \Bigg) \nonumber    \\
  &+& \sum_{\substack{ \text{terminal node } \tau \\ \text{ outside } tree(i)   \\ V_{\text{box}(\tau)} \leq \sigma_m } }  \operatorname{Pr} \left[ \pi \text{ reaches } \tau \mid T_i \notin G_i \right]   \mathbb{E} \left[ V_{\text{box}(\tau)} \mid V_{\text{box}(\tau)} \leq \sigma_m \right]  \nonumber \\
  &\leq& \sum_{\substack{ \text{interior node } \eta \\ \text{ outside } tree(i)   \\ \text{action} (\eta)= \text{F-open} \\ \sigma_{\text{box}(\eta)} \leq \sigma_m  }}  \operatorname{Pr} \left[ \pi \text{ reaches } \eta \mid T_i \notin G_i \right] \Big(  \operatorname{Pr} \left[ V_{\text{box}(\eta) } > \sigma_m \right] \cdot \sigma_m \Big) \nonumber    \\
  &+& \sum_{\substack{ \text{interior node } \eta \\ \text{ outside } tree(i)   \\ \text{action} (\eta)= \text{P-open} }}  \operatorname{Pr} \left[ \pi \text{ reaches } \eta \mid T_i \notin G_i \right]  \Bigg(  \operatorname{Pr} \left[ \sigma_{\text{box}(\eta)}^{F \mid t_{\text{box}(\eta)}} > \sigma_m   \right] \operatorname{Pr} \left[  V_{\text{box}(\eta)} > \sigma_m ~\middle \vert~ \sigma_{\text{box}(\eta)}^{F \mid t_{\text{box}(\eta)}} > \sigma_m  \right] \cdot \sigma_m   \nonumber   \Bigg) \nonumber \\
  &+& \sum_{\substack{ \text{terminal node } \tau \\ \text{ outside } tree(i)   \\ V_{\text{box}(\tau)} \leq \sigma_m }}  \operatorname{Pr} \left[ \pi \text{ reaches } \tau \mid T_i \notin G_i \right]  \cdot \sigma_m  \nonumber \\
   &=& \Bigg( \sum_{ \substack{ \text{terminal node } \tau \\ \text{ outside } tree(i) }    }  \operatorname{Pr}\left[ \pi \text{ reaches } \tau \mid T_i \notin G_i \right] \Bigg) \cdot \sigma_m   \nonumber \\
  &=& \left( 1- \theta_i^{\pi} \right) \cdot \sigma_m.  \nonumber
\end{eqnarray}

  The above inequality is due to the following two facts:
   \begin{itemize}
     \item {\em Fact~1:} For any closed box $j$, by the definition of the F-threshold and monotonicity of the function  $ \mathbb{E} \left [ ( V_j  -  x )^+  \right]$ in $x$, we obtain $c_j^F \geq  \widetilde{ c_j^F}  \triangleq \mathbb{E} \left [ ( V_j  -  \sigma_m )^+  \right] $, which follows because $\sigma_m \geq \sigma_j^F$. Thus,
         \begin{equation}\label{eq:cost_accounting_ineq_1}
             \operatorname{Pr} \left[  V_j > \sigma_m \right] \sigma_m = - \widetilde{ c_j^F} +  \operatorname{Pr} \left[  V_j > \sigma_m \right]  \mathbb{E}\left[   V_j \mid V_j > \sigma_m \right]  \geq -  c_j^F +  \operatorname{Pr} \left[  V_j > \sigma_m \right]  \mathbb{E}\left[   V_j \mid V_j > \sigma_m \right].\nonumber
         \end{equation}
     \item  {\em Fact~2:} For any closed box $j$, by definition of the P-threshold and the monotonicity of $ \mathbb{E} \left[ \max \left\{ 0, - c_j^F + \mathbb{E}[ ( V_j - x )^+ ]  \right \} \right ]$ in $x$, we obtain $c_j^P \geq  \widetilde{ c_j^P}  \triangleq \mathbb{E} \left[ \max \left\{ 0, - c_j^F + \mathbb{E}[ ( V_j - \sigma_m )^+ ]  \right \} \right ]  $ since $\sigma_m \geq \sigma_j^P$. Thus,
  \begin{eqnarray}
     & & - c_j^P + \operatorname{Pr} \left[ \sigma_j^{F \mid T_j} > \sigma_m   \right] \left(  -c_j^F + \operatorname{Pr} \left[  V_j > \sigma_m ~\middle\vert~ \sigma_j^{F \mid T_j} > \sigma_m  \right] \mathbb{E} \left[  V_j ~\middle\vert~ V_j > \sigma_m ,  \sigma_j^{F \mid T_j} > \sigma_m \right]    \right) \nonumber \\
     &\leq &  - \widetilde{ c_j^P} + \operatorname{Pr} \left[ \sigma_j^{F \mid T_j} > \sigma_m   \right] \left(  -c_j^F + \operatorname{Pr} \left[  V_j > \sigma_m ~\middle\vert~ \sigma_j^{F \mid T_j} > \sigma_m  \right] \mathbb{E} \left[  V_j ~\middle\vert~ V_j > \sigma_m ,  \sigma_j^{F \mid T_j} > \sigma_m \right]    \right)  \nonumber  \\
     &=& \operatorname{Pr} \left[ \sigma_j^{F \mid T_j} > \sigma_m   \right] \operatorname{Pr} \left[  V_j > \sigma_m ~\middle\vert~ \sigma_j^{F \mid T_j} > \sigma_m  \right] \sigma_m . \label{eq:cost_accounting_ineq_2}\nonumber
  \end{eqnarray}
 \end{itemize}
 
\end{myproof2}

\end{myproof2}


\subsection{Proof of Theorem~\ref{thm:just_weak_closed}}
\label{appendix:thm_just_weak_closed}

We start by establishing an auxiliary lemma that states an optimal policy should not F-open a well-classified box. We then proceed to prove Theorem~\ref{thm:just_weak_closed}.


\begin{lemma}\label{lemma:well_classified_F_dominated}
For every state $(\mathcal{C}, \mathcal{P}, y)$, F-opening a well-classified box $i \in \mathcal{C}$ is suboptimal. 
\end{lemma}

\begin{myproof2}{Lemma \ref{lemma:well_classified_F_dominated}}

 We prove this by contradiction. 
 Suppose that in the current state 
 $(\mathcal{C}, \mathcal{P}, y)$ an optimal policy $\pi$ F-opens box $i$. In such case, the expected profit can be written as
  \begin{eqnarray}
    J^{\pi} (\mathcal{C}, \mathcal{P}, y) &=& - c_i^F + \mathbb{E}\left[  J^{\pi} (\mathcal{C} \setminus \{i \}, \mathcal{P}, \max\left\{ y, V_i \right\} )    \right]  \nonumber \\
     &=& -c_i^F +  \sum_{t_i: \sigma_i^{F \mid t_i} > \sigma_{-i}} \operatorname{Pr}\left[T_i=t_i \right]  \cdot  \mathbb{E}\left[ J^{\pi}  (\mathcal{C} \setminus \{i \}, \mathcal{P}, \max\left\{ y, V_i \right\} ) \mid T_i=t_i\right]   \nonumber \\
     &+&  \sum_{t_i: \sigma_i^{F \mid t_i} \leq \sigma_{-i} } \operatorname{Pr}\left[T_i=t_i \right]  \cdot \mathbb{E}\left[ J^{\pi}  (\mathcal{C} \setminus \{i \}, \mathcal{P}, \max\left\{ y, V_i \right\} ) \mid T_i=t_i\right] .    \nonumber
  \end{eqnarray}

We define an alternative policy $\pi'$ and show that it attains a higher expected profit than policy $\pi$. 
At state $ (\mathcal{C}, \mathcal{P}, y)$, policy $\pi'$ P-opens box $i$.  
If the observed type $t_i$ satisfies $ \sigma_i^{F \mid t_i} > \sigma_{-i}$, then policy $\pi'$ F-opens box $i$ and imitates policy $\pi$ thereafter. 
Otherwise, if $ \sigma_i^{F \mid t_i} \leq \sigma_{-i}$, then instead of F-opening the partially open box $i$, policy $\pi'$ generates an independent sample denoted by $\hat{v_i}$ from the prize distribution of $V_i$ conditional on $T_i=t_i$. 
Policy $\pi'$ treats $\hat{v_i}$ as the realized prize of box $i$ and imitates policy $\pi$ afterward, with the only difference that, whenever policy $\pi$ selects box $i$, policy $\pi'$ selects the box whose value is $y$. 
Therefore, the expected profit of policy $\pi'$ can be expressed as follows:
  \begin{eqnarray}
    J^{\pi'} (\mathcal{C}, \mathcal{P}, y) &=&  - c_i^P + \sum_{t_i: \sigma_i^{F \mid t_i} > \sigma_{-i}} \operatorname{Pr}\left[T_i=t_i \right] \left( -c_i^F + \mathbb{E} \left[ J^{\pi} (\mathcal{C} \setminus \{i \}, \mathcal{P}, \max\left\{ y, V_i \right\} )  \mid T_i=t_i \right] \right) \nonumber  \\
     &+&  \sum_{t_i: \sigma_i^{F \mid t_i} \leq \sigma_{-i} } \operatorname{Pr}\left[T_i=t_i \right] \cdot J^{\pi'} \left(\mathcal{C} \setminus \{i \}, \mathcal{P} \cup \{(i,t_i) \}  , y \right) . \nonumber
  \end{eqnarray}
  It follows that the difference in the expected profits between the two policies satisfies
  \begin{eqnarray}  % \underbrace{\{(i,t_i) \}}_{\text{expired}}
  & & J^{\pi'} (\mathcal{C}, \mathcal{P}, y) - J^{\pi} (\mathcal{C}, \mathcal{P}, y)   \nonumber \\
    &=&  - c_i^P +  \sum_{t_i: \sigma_i^{F \mid t_i} \leq \sigma_{-i} } \operatorname{Pr}\left[T_i=t_i \right] \left( c_i^F + J^{\pi'} \left(\mathcal{C} \setminus \{i \}, \mathcal{P} \cup \{(i,t_i) \}  , y \right) - \mathbb{E}\left[ J^{\pi}  (\mathcal{C} \setminus \{i \}, \mathcal{P}, \max\left\{ y, V_i \right\} ) \mid T_i=t_i\right]  \right)   \nonumber   \\
    &=& - c_i^P +  \sum_{t_i: \sigma_i^{F \mid t_i} \leq y } \operatorname{Pr}\left[T_i=t_i \right] \left( c_i^F + J^{\pi'} \left(\mathcal{C} \setminus \{i \}, \mathcal{P} \cup \{(i,t_i) \}   , y \right) - \mathbb{E}\left[ J^{\pi}  (\mathcal{C} \setminus \{i \}, \mathcal{P}, \max\left\{ y, V_i \right\} ) \mid T_i=t_i\right]  \right)  \nonumber \\ %  \label{eq:lemma_sufficient_F_dominated_1} \underbrace{\{(i,t_i) \}}_{\text{F-expired}} \\
    &\geq& - c_i^P +  \sum_{t_i: \sigma_i^{F \mid t_i} \leq y } \operatorname{Pr}\left[T_i=t_i \right] \left( c_i^F - \mathbb{E} \left[ \left( V_i - y \right)^+  ~\middle \vert~ T_i=t_i \right] \right)   \label{eq:lemma_sufficient_F_dominated_2}. %  \\
    % &=& - \Delta_i^{F,P}(y) . \nonumber
  \end{eqnarray}
The second equation follows from the assumption that box $i$ is well-classified.
The inequality holds since the difference in the total expected profits garnered by policies $\pi'$ and $\pi$ is at most $(V_i - y)^+$ on any sample path.
We note that equation~\eqref{eq:lemma_sufficient_F_dominated_2} is exactly the negative of 
equation~\eqref{eq:lemma:monotonicity_myopic_gain_SW}. 
Therefore, by Theorem~\ref{thm:myopic_stopping}, we have $ J^{\pi'} (\mathcal{C}, \mathcal{P}, y) - J^{\pi} (\mathcal{C}, \mathcal{P}, y)  > 0$, provided that $y > \sigma_i^{F/P} $ (which holds since box $i$ is well-classified box).
\end{myproof2}


\begin{myproof2}{Theorem~\ref{thm:just_weak_closed}}
Similarly to the proof of Lemma~\ref{lemma:just_strong_partial},  we prove the theorem by induction over the integer $2  \mid \mathcal{C} \mid + \mid \mathcal{P} \mid  $, which corresponds to the maximal possible number of openings from state $({\cal C},{\cal P},y)$ onwards. 
  \begin{itemize}
    \item {\em Base case: $2  \mid \mathcal{C} \mid + \mid \mathcal{P} \mid  = 2$.} There is only one closed box. The well-classified condition is clearly satisfied, since the problem reduces to the single box case. % in Example~\ref{ex:single_box}. 
    The desired claim immediately follows from Theorem~\ref{thm:myopic_stopping}.
\begin{figure}[htbp]
\centering
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{graphs/just_weak_interchange_base_policy_pi.png}
    \caption{Policy $\pi$}
   \label{fig:just_weak_interchange_base_policy_1}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{graphs/just_weak_interchange_base_policy_pi_prime.png}
  \caption{Policy $\pi'$}
  \label{fig:just_weak_interchange_base_policy_2}
\end{subfigure}
\caption{ A graphical illustration of policy $\pi$ and policy $\pi'$, for the base case $2  \mid \mathcal{C} \mid + \mid \mathcal{P} \mid  = 3$ in the proof of Theorem~\ref{thm:just_weak_closed}.   }
\label{fig:just_weak_interchange_base_policy}
\end{figure}
    \item {\em Base case: $2  \mid \mathcal{C} \mid + \mid \mathcal{P} \mid  = 3$.} Let $i$ be the single box contained in ${\cal C}$ and let $j$ be the single box contained in ${\cal P}$. 
    By Lemma~\ref{lemma:well_classified_F_dominated}, F-opening box $i$ is suboptimal. 
    As such, suppose that an optimal policy $\pi$ does not P-open box $i$, and instead it F-opens box $j$, and then the system transitions to a state in which $2  \mid \mathcal{C} \mid + \mid \mathcal{P} \mid  = 2$.
    By Theorem~\ref{thm:myopic_stopping}, policy $\pi$ selects box $j$ if $V_j > \sigma_i^P$. Otherwise, when $V_j \leq \sigma_i^P$, we observe that box $i$ is the only one remaining and it is still well-classified, therefore Theorem~\ref{thm:myopic_stopping} implies that policy $\pi$ proceeds to P-open this box.
    Applying Theorem~\ref{thm:just_strong}, policy $\pi$ then F-opens box $i$ if the revealed type $t_i$ is such that $\sigma_i^{F \mid t_i} > \sigma_i^P$, and further selects box $i$ if $V_i > \sigma_i^P$ (this follows from Theorem~\ref{thm:myopic_stopping}). The policy is illustrated in Figure~\ref{fig:just_weak_interchange_base_policy_1}.
    We let $q_i = \operatorname{Pr} \left[ \sigma_i^{F \mid T_i} > \sigma_i^P  \right]$, $p_i = \operatorname{Pr} \left[ V_i > \sigma_i^P   \middle \vert \sigma_i^{F \mid t_i} > \sigma_i^P  \right]$, and $p_j =  \operatorname{Pr} \left[ V_j > \sigma_i^P  \right]$.     
    Therefore, the expected profit evaluated in state $(\{ i\}, \{ j \}, y)$ is
        \begin{eqnarray}
          & &J^{\pi}((\{ i\}, \{ j \}, y)) \nonumber\\
          &=& -c_j^F +  p_j \cdot \mathbb{E}\left[V_j \mid V_j > \sigma_i^P  \right]  \nonumber \\
          &+& (1-p_j) \cdot  \Bigg( -c_i^P + q_i \Big( -c_i^F + p_i \cdot \mathbb{E} \left[ V_i \mid V_i > \sigma_i^P \right] + (1-p_i) \cdot \mathbb{E} \left[ \max \{y, V_i, V_j \} \mid V_i \leq \sigma_i^P, V_j \leq \sigma_i^P\right] \Big)  \nonumber \\
           &+&   (1-q_i) \cdot \mathbb{E}\left[ J^{\pi}((\emptyset, \{ (i,t_i) \}, \max\{y, V_j \}))  ~\middle\vert~ V_j \leq \sigma_i^P, \sigma_i^{F \mid t_i} \leq \sigma_i^P   \right] \Bigg).   \nonumber
        \end{eqnarray}

        We construct an alternative policy $\pi'$ that P-opens box $i$ in state $(\{ i\}, \{ j \}, y)$, as specified in Figure~\ref{fig:just_weak_interchange_base_policy_2}.
        The expected profit generated by policy $\pi'$ is
        \begin{eqnarray}
          J^{\pi'}((\{ i\}, \{ j \}, y)) &=&  -c_i^P + q_i \cdot \Bigg(  -c_i^F + p_i \cdot  \mathbb{E} \left[ V_i \mid V_i > \sigma_i^P \right]  \nonumber \\
          &+&  (1-p_i) \cdot  \Big( - c_j^F + p_j \cdot \mathbb{E}\left[V_j \mid V_j > \sigma_i^P  \right]  + (1-p_j) \cdot \mathbb{E} \left[ \max \{y, V_i, V_j \} \mid V_i \leq \sigma_i^P, V_j \leq \sigma_i^P\right]   \Big)   \Bigg)         \nonumber \\
          &+&  (1-q_i)  \cdot  \Bigg( -c_j^F + p_j \cdot \mathbb{E} \left[ V_j \mid V_j > \sigma_i^P \right]     \nonumber \\
          &+&  (1-p_j) \cdot \mathbb{E}\left[ J^{\pi}((\emptyset, \{ (i,t_i) \}, \max\{y, V_j \}))  ~\middle\vert~ V_j \leq \sigma_i^P, \sigma_i^{F \mid t_i} \leq \sigma_i^P   \right]  \Bigg). \nonumber
        \end{eqnarray}
        The difference between the expected profit obtained by the two policies is
        \begin{eqnarray}
        & & J^{\pi'}((\{ i\}, \{ j \}, y)) -  J^{\pi}((\{ i\}, \{ j \}, y))\nonumber \\
            &=&  \left(-q_i(1-p_i) - (1-q_i) +1 \right) \cdot c_j^F + \left( -1 +(1-p_j) \right) \cdot c_i^P + \left( -q_i + q_i(1-p_j) \right) \cdot c_i^F  \nonumber  \\
           &+& \left(  q_{i} p_{i}-\left(1-p_{j}\right)  q_{i}  p_{i} \right) \cdot \mathbb{E} \left[ V_i \mid V_i > \sigma_i^P \right] + \left( q_{i} \left(1-p_{i}\right) p_{j}+\left(1-q_{i}\right)  p_{j} - p_{j}  \right) \cdot \mathbb{E} \left[ V_j \mid V_j > \sigma_i^P \right]   \nonumber \\
           &=& p_{j} \cdot  \left(-c_{i}^{P} - q_{i} c_{i}^{F} + q_{i} p_{i} \cdot  \mathbb{E}\left[V_{i} \mid V_{i}>\sigma_{i}^{P}\right]\right)  - p_i q_i \cdot  \left( -c_{j}^{F}+p_{j} \cdot \mathbb{E}\left[V_{j} \mid V_j>\sigma_{i}^{p}\right] \right)  \nonumber \\
           &=& p_j q_i p_i  \cdot \sigma_i^P  - p_i q_i  \cdot  \left( -c_{j}^{F}+p_{j} \cdot \mathbb{E}\left[V_{j} \mid V_j>\sigma_{i}^{p}\right] \right)  \nonumber \\
           &\geq&  p_j q_i p_i  \cdot \sigma_i^P  - p_i q_i p_j  \cdot \sigma_i^P  \nonumber   \\
           &=& 0.  \nonumber
        \end{eqnarray}
        The inequality holds due to the same reasoning as in the derivation of equation~\eqref{eq:cost_accounting_ineq_1}. % This contradicts the optimality of policy $\pi$.
        Hence, policy $\pi'$ can achieve an expected profit as high as policy $\pi$. 
    
    \item {\em Induction step.} Suppose that the induction hypothesis holds when  $2  \mid \mathcal{C} \mid + \mid \mathcal{P} \mid  = 2, 3, \cdots, n$ with $n \geq 3$. 
    We wish to establish a similar claim when $2  \mid \mathcal{C} \mid + \mid \mathcal{P} \mid  =n + 1$. 
    Suppose an optimal policy $\pi$ does not P-open immediately.  
    We show that we can construct alternative policies that perform at least as well as policy $\pi$.  
    Depending on whether policy $\pi$ F-opens or P-opens a box next, we distinguish between the following two cases. 
\begin{figure}[htbp]
\centering
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{graphs/just_weak_interchange_ww_policy_pi.png}
    \caption{Policy $\pi$}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{graphs/just_weak_interchange_ww_policy_pi_prime.png}
  \caption{Policy $\pi'$}
\end{subfigure}
\caption{ Graphical illustration of policy $\pi$ and policy $\pi'$, for Case~1 in the induction step, in the proof of Theorem~\ref{thm:just_weak_closed}.   }
\label{fig:just_weak_interchange_ww_policy}
\end{figure}

    \paragraph{Case~1: Policy $\pi$ starts by P-opening.}
           Suppose that policy $\pi$ P-opens a box $j \in \mathcal{C}$ (without loss of generality, we assume has not expired). Consequently, the system  transitions to a state $(\mathcal{C}', \mathcal{P}', y)$ for which $2  \mid \mathcal{C} ' \mid  + \mid \mathcal{P}' \mid  = n-1$. By Theorem~\ref{thm:just_strong}, if the type $T_j$ is found to be such that $\sigma_j^{F \mid T_j} > \sigma_i^P$, policy $\pi$ will further F-open box $j$, and select box $j$ if $V_j > \sigma_i^P$ according to Theorem~\ref{thm:myopic_stopping}. If $V_j\leq \sigma_i^P$, policy $\pi$ will P-open box $i$ by the induction hypothesis, since box $i$ remains well-classified, and $\sigma_i^{P}$ is still the largest threshold. Otherwise, if $\sigma_j^{F \mid T_j} \leq \sigma_i^P$, by the induction hypothesis, policy $\pi$ will P-open box $i$. 
           Let $q_k = \operatorname{Pr} \left[ \sigma_k^{F \mid T_k} > \sigma_i^P  \right] $ and $p_k = \operatorname{Pr} \left[ V_k > \sigma_i^P  \mid \sigma_k^{F \mid t_k} > \sigma_i^P \right]$ for each box $k \in \{i, j\}$. 
           With this definition at hand, the expected profit obtained by policy $\pi$ can be written as
          \begin{eqnarray}
          J^{\pi}( \mathcal{C}, \mathcal{P}, y)  &=& -c_{j}^{P}+q_{j} \cdot \Bigg ( -c_{j}^{F}+p_{j} \cdot E\left[V_{j}  \mid V_{j}>\sigma_{i}^{P} \right]  \nonumber \\
          &+& (1-p_j) \Big( -c_{i}^{P} + q_{i} \left( -c_{i}^{F} + p_{i} \cdot \mathbb{E}\left[V_{i} \mid V_{i} >  \sigma_{i}^{P} \right] + \left( 1 - p_{i} \right) \cdot J_{1} \right) + (1-q_i) \cdot J_2  \Big) \Bigg)   \nonumber \\
          &+& (1-q_j) \Bigg( -c_i^P + q_i \Big( -c_i^F + p_i \cdot \mathbb{E} \left[ V_i \mid V_i > \sigma_i^P  \right] +(1-p_i) \cdot J_3   \Big) + (1-q_i) \cdot J_4   \Bigg)  , \nonumber
        \end{eqnarray}
           where $J_1 = \mathbb{E}\left[J^{\pi}( \mathcal{C} \setminus \{i,j \}, \mathcal{P}, \max\{y, V_i, V_j \}) ~\middle\vert~  \sigma_j^{F \mid T_j} > \sigma_i^P, V_j \leq \sigma_i^P, \sigma_i^{F\mid T_i} > \sigma_i^P, V_i \leq \sigma_i^P \right]$ ,\\
            $J_2 = \mathbb{E}\left[ J^{\pi}( \mathcal{C} \setminus \{i,j \}, \mathcal{P} \cup \{(i, t_i) \}, \max\{y,  V_j \})   ~\middle\vert~  \sigma_j^{F \mid T_j} > \sigma_i^P, V_j \leq \sigma_i^P, \sigma_i^{F\mid T_i} \leq \sigma_i^P \right]$ , \\
           $J_3 = \mathbb{E}\left[ J^{\pi}( \mathcal{C} \setminus \{i,j \}, \mathcal{P} \cup \{(j, T_j) \}, \max\{y, V_i \})  ~\middle\vert~   \sigma_j^{F \mid T_j} \leq \sigma_i^P,  \sigma_i^{F\mid T_i} > \sigma_i^P, V_i \leq \sigma_i^P \right]$ , \\
           $J_4 = \mathbb{E}\left[ J^{\pi}( \mathcal{C} \setminus \{i,j \}, \mathcal{P} \cup \{(j, T_j), (i, t_i) \}, y )  ~\middle\vert~   \sigma_j^{F \mid T_j} \leq \sigma_i^P,  \sigma_i^{F\mid T_i} \leq \sigma_i^P   \right]$.

           We construct an alternative policy $\pi'$ that P-opens box $i$ in state $( \mathcal{C}, \mathcal{P}, y) $, as specified in Figure~\ref{fig:just_weak_interchange_ww_policy}. The expected profit in state $( \mathcal{C}, \mathcal{P}, y)$ under policy $\pi'$ is
           \begin{eqnarray}
            J^{\pi'}( \mathcal{C}, \mathcal{P}, y) &=&   -c_{i}^{P} + q_{i} \Bigg ( -c_{i}^{F}+p_{i}  \mathbb{E} \left[V_{i}  \mid V_{i} > \sigma_{i}^{P} \right]  \nonumber \\
          &+& (1-p_i) \Big( -c_{j}^{P} + q_{j} \left( -c_{j}^{F} + p_{j} \cdot \mathbb{E}\left[V_{j} \mid V_{j} >  \sigma_{i}^{P} \right] + \left( 1 - p_{j} \right) \cdot J_{1} \right) + (1-q_j) \cdot J_3  \Big) \Bigg)   \nonumber \\
          &+& (1-q_i) \Bigg( -c_j^P + q_j \Big(-c_j^F + p_j \cdot \mathbb{E} \left[ V_j \mid V_j > \sigma_i^P  \right] +(1-p_j) \cdot J_2   \Big) + (1-q_j) \cdot J_4   \Bigg) . \nonumber
           \end{eqnarray}
           Consequently, the difference between the expected profits under policies $\pi'$ and $\pi$ is 
           \begin{eqnarray}
              & &  J^{\pi'}( \mathcal{C}, \mathcal{P}, y)  - J^{\pi}( \mathcal{C}, \mathcal{P}, y)  \nonumber  \\
              &=&  \left( -1 + q_j (1-p_j) + (1-q_j)\right) \cdot c_i^P +  \left( -q_i + q_j (1-p_j) q_i + (1-q_j) q_i  \right) \cdot c_i^F     \nonumber  \\
              &+&    \left( -q_i (1-p_i) - (1-q_i) + 1 \right) \cdot c_j^P +    \left( -q_i(1-p_i)q_j - (1-q_i)q_j + q_j \right) \cdot  c_j^F    \nonumber  \\
              &+&  \left( q_{i} p_{i}- q_{j} \left(1-p_{j}\right) q_{i} p_{i} - \left( 1-q_{j} \right) q_{i} p_{i} \right) \cdot \mathbb{E} \left[V_{i}  \mid V_{i} > \sigma_{i}^{P} \right]         \nonumber  \\
              &+&   \left( q_{i} \left(1-p_{i}\right) q_{j} p_{j}+\left(1-q_{i}\right)  q_{j} p_{j} - q_{j} p_{j} \right) \cdot  \mathbb{E} \left[V_{j}  \mid V_{j} > \sigma_{i}^{P} \right]   \nonumber \\
              &=& -q_j p_j c_i^P - q_j p_j q_i c_i^F + q_j p_j q_i p_i  \cdot \mathbb{E} \left[V_{i}  \mid V_{i} > \sigma_{i}^{P} \right]  \nonumber \\
              &+& q_{i} p_{i} c_{j}^{P} + q_{i} p_{i} q_{j} c_{j}^{F} - q_{i} p_{i} q_{j} p_{j} \cdot  \mathbb{E}\left[V_{j} \mid V_j>\sigma_{i}^{p}\right]       \nonumber \\
              &=& q_j p_j  \cdot \left( - c_i^P -  q_i c_i^F + q_i p_i \cdot \mathbb{E} \left[V_{i}  \mid V_{i} > \sigma_{i}^{P} \right]    \right) \nonumber \\
              &-& q_{i} p_{i}  \cdot \left( - c_{j}^{P} - q_{j} c_{j}^{F} + q_{j} p_{j} \cdot \mathbb{E}\left[V_{j} \mid V_j>\sigma_{i}^{p}\right]  \right)        \nonumber \\
              &=& q_j p_j q_i p_i \cdot  \sigma_i^P -q_{i} p_{i}  \cdot \left( - c_{j}^{P} - q_{j} c_{j}^{F} + q_{j} p_{j} \cdot \mathbb{E}\left[V_{j} \mid V_j>\sigma_{i}^{p}\right]  \right)   \nonumber \\
              &\geq& q_j p_j q_i p_i \cdot \sigma_i^P - q_{i} p_{i} q_j p_j \cdot \sigma_i^P \nonumber \\
              &=& 0  . \nonumber
           \end{eqnarray}
           The last inequality is due to the same reasoning as in equation~\eqref{eq:cost_accounting_ineq_2}. % This contradicts the optimality of policy $\pi$.
           Hence, policy $\pi'$ can achieve an expected profit as high as policy $\pi$. 
\begin{figure}[htbp]
\centering
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=0.85\linewidth]{graphs/just_weak_interchange_sw_policy_pi.png}
    \caption{Policy $\pi$}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=0.85\linewidth]{graphs/just_weak_interchange_sw_policy_pi_prime.png}
  \caption{Policy $\pi'$}
\end{subfigure}
\caption{ Graphical illustration of policy $\pi$ and policy $\pi'$, for Case 2 in the induction step, in the proof of Theorem~\ref{thm:just_weak_closed}.   }
\label{fig:just_weak_interchange_sw_policy}
\end{figure}
\paragraph{Case~2: Policy $\pi$ starts by F-opening.}
    Suppose that policy $\pi$ F-opens a box $j \in \mathcal{C}$. % (which without loss of generality, we assume has not expired). 
    Consequently, the system transitions to a state $(\mathcal{C}', \mathcal{P}', y')$ for which $2  \mid \mathcal{C} ' \mid  + \mid \mathcal{P}' \mid  = n-1$. Alternatively, if we suppose that policy $\pi$ F-opens a box $j \in \mathcal{P}$, then it transitions to a state $(\mathcal{C}', \mathcal{P}', y')$ for which $2  \mid \mathcal{C} ' \mid  + \mid \mathcal{P}' \mid  = n$. Observe that, in both settings, box $i$ will remain well-classified. Indeed, after box $j$ is opened, if it is suboptimal to stop, then the P-threshold of box $i$ is still the largest opening threshold. Hence, in view of the induction hypothesis, policy $\pi$ will P-open box $i$. 
    Let $p_j = \operatorname{Pr} \left[ V_j > \sigma_i^{P}\right]$, $q_i = \operatorname{Pr} \left[ \sigma_i^{F \mid T_i}  >  \sigma_i^{P} \right] $ and $p_i = \operatorname{Pr} \left[ V_i > \sigma_i^{P} \mid  \sigma_i^{F\mid T_i}  >  \sigma_i^{P} \right]$. 
    The expected profit in state $( \mathcal{C}, \mathcal{P}, y)$ under policy $\pi$ is
      \begin{eqnarray}
    J^{\pi}( \mathcal{C}, \mathcal{P}, y) &=&  - c_j^F + p_j \cdot \mathbb{E} \left[ V_j \mid V_j > \sigma_i^P \right]  + (1-p_j) \cdot \Bigg( -c_i^P + q_i \left[ -c_i^F + p_i \cdot \mathbb{E} \left[V_i \mid V_i > \sigma_i^P \right] \right]  \nonumber \\
    &+& q_i (1-p_i) \cdot J_1 + (1-q_i) \cdot J_2 \Bigg). \nonumber
    \end{eqnarray}
    
    We construct an alternative policy $\pi'$ that P-opens box $i$ first, as specified in Figure \ref{fig:just_weak_interchange_sw_policy}. The expected profit in state $( \mathcal{C}, \mathcal{P}, y)$ under policy $\pi'$ is
    \begin{eqnarray}
    & & J^{\pi'}( \mathcal{C}, \mathcal{P}, y) \nonumber \\
    &=&  -c_i^P + q_i \cdot \Big( -c_i^F + p_i \cdot  \mathbb{E} \left[ V_i \mid V_i > \sigma_i^P \right] + (1-p_i) \left( -c_j^F + p_j \cdot  \mathbb{E} \left[ V_j \mid V_j > \sigma_i^P \right] + (1-p_j) \cdot J_1  \right) \Big) \nonumber \\
    &+& (1-q_i ) \cdot \Big(  -c_j^F + p_j \cdot  \mathbb{E} \left[ V_j \mid V_j > \sigma_i^P \right]  + (1-p_j) \cdot J_2 \Big).      \nonumber
    \end{eqnarray}
    Hence, the difference in the expected profits under policies $\pi'$ and $\pi$ is
    \begin{eqnarray}
      & &  J^{\pi'}( \mathcal{C}, \mathcal{P}, y)  - J^{\pi}( \mathcal{C}, \mathcal{P}, y)  \nonumber  \\
      &=&  \left( -1 + 1 - p_j \right) \cdot c_i^P +  \left( -q_i + (1-p_j) q_i  \right) \cdot c_i^F +  \left(-q_i (1-p_i) - (1-q_i) + 1 \right) \cdot  c_j^F    \nonumber  \\
      &+&  \left(q_i p_i - (1-p_j) q_i p_i \right) \cdot \mathbb{E} \left[V_{i}  \mid V_{i} > \sigma_{i}^{P} \right]  + \left( q_i (1-p_i) p_j + (1-q_i)p_j - p_j \right) \cdot  \mathbb{E} \left[ V_{j}  \mid V_{j} > \sigma_{i}^{P}  \right]        \nonumber  \\
      &=& p_j \cdot  \left( -c_i^P - q_i c_i^F + q_i p_i \cdot \mathbb{E} \left[V_{i}  \mid V_{i} > \sigma_{i}^{P} \right]   \right)  - q_i p_i \cdot \left( -c_j^F + p_j \cdot \mathbb{E} \left[V_{j}  \mid V_{j} > \sigma_{i}^{P} \right]  \right)   \nonumber \\
      &=& p_j  q_i p_i \cdot \sigma_i^P  - q_i p_i \cdot \left( -c_j^F + p_j \cdot \mathbb{E} \left[V_{j}  \mid V_{j} > \sigma_{i}^{P}   \right]  \right)      \nonumber \\
      &\geq & p_j  q_i p_i  \cdot \sigma_i^P  - p_j  q_i p_i  \cdot \sigma_i^P   = 0 .        \nonumber
    \end{eqnarray}
    The inequality follows from the same reasoning as the derivation of  equation~\eqref{eq:cost_accounting_ineq_1}. % This contradicts the optimality of policy $\pi$.
    Hence, policy $\pi'$ can achieve an as high expected profit as policy $\pi$. This concludes the proof of the induction step.% for $2  \mid \mathcal{C} \mid + \mid \mathcal{P} \mid  =n + 1$.
  \end{itemize}
\end{myproof2}






\subsection{Proof of Theorem~\ref{thm:iid_optimal}}
\label{sec:proof_iid_optimal}

We first introduce notation prior to proceeding to prove each of the five properties. 
Since boxes are identical, for brevity, we drop the subscript of box indices throughout this proof. 
Recall that each box can be of either a good type (G) or a bad type (B), and the rewards are binary with values 0 or 1.
Let $p^G$ and $p^B$ denote the probabilities of a box being of good type and bad type, respectively. Conditional on the box being of good (bad) type, the probability that it contains a reward is $q^G$ ($q^B$).

To encode the state space, it suffices to record the number of closed boxes $n_C$, the number of good-type boxes $n_G$, the number of bad-type boxes $n_B$ and the current best reward: $(n_C, n_G, n_B, y)$. The initial state is then $(n, 0, 0, 0)$. 
Since a good type will be F-opened immediately upon observation and it is optimal to stop once a prize is found, we can ``skip'' states in which good-type boxes were discovered and ``collapse'' states where the reward was found, to obtain a more compact representation using the tuple $(n_C, n_B)$. 
Finally, we denote by $J^F$ ($J^P$) the expected payoff of F-opening (P-opening) a closed box and then following the optimal policy at any state $(n_C, n_B)$ with at least one closed box ($n_C \geq 1$). 

We proceed to prove each stated property. 


\textbf{Property: Policy $\pi$ assigns the highest priority to F-opening good-type boxes.} 
Applying Observation~\ref{obs:thresholds_order} to the two-type case, we observe that 
\begin{enumerate}
    \item $\sigma^{F/P} < \sigma^{F} \leq \sigma^{P}$ 
    (the theorem assumes that $\sigma^{F} < \sigma^{P}$), and
    \item $\sigma^{F|B} \leq \sigma^{F / P }$ and $\sigma^{F | G} \geq \sigma^P$.    
\end{enumerate}
Theorem~\ref{thm:just_strong} then implies that an optimal policy directly F-opens a good type upon its discovery. 

\textbf{Property: Policy $\pi$ either discards all bad-type boxes, or  assigns the lowest priority to F-opening them.} 
We consider two cases, depending on whether $\sigma^{F|B}$ is positive. 
For the case when $\sigma^{F|B} \leq 0$, a bad type is not worth opening. 
For the case when $\sigma^{F|B} >0$, the property can be proven by an interchange argument. For brevity, the proof is omitted. 




\textbf{Property: Policy $\pi$ is a committing policy.}     
To show that there exists an optimal policy that is a committing policy (see Section~\ref{subsec:apx_policies} for a formal definition and discussion), we first prove that the presence of bad-type boxes does \textit{not} affect the decision to F-open versus P-open the closed boxes. We formalize this in the following lemma, which for ease of reading we defer proving to the end of this section.

\begin{lemma} \label{lemma:iid_diff_not_func_of_nb}
    For a PSI-B2I instance at state $(n_C, n_B)$ where $n_C \geq 1$, 
    the difference $J^F(n_C, n_B) - J^P(n_C, n_B)$ is a function of $n_C$ and is independent of $n_B$.
    % is constant with respect to $n_B$.
\end{lemma}

Recall from Theorem~\ref{thm:myopic_stopping} that at state $(1, 0)$, it is optimal to F-open the closed box (see for illustration Figure~\ref{fig:example_1}). Lemma~\ref{lemma:iid_diff_not_func_of_nb} then implies that at any state $(1, n_B)$, it is optimal to F-open the closed box. 
The latter serves as a basis for an inductive argument for the optimal policy being a committing policy. At a state $(n_C, n_B)$, the difference in the expected costs between F-opening versus P-opening depends on actions taken at future states of the form $(n_C-1, n_B)$ and $(n_C-1, n_B+1)$, that are reached depending on the opening mode and whether the opened job is of a bad type or not. Regardless, the policy takes  actions that are independent of the number of bad-type boxes, meaning that whether or not P-opening or F-opening is better at state $(n_C, n_B)$, one can already commit at that state to the opening mode of each of the remaining boxes. 




\textbf{Property: There exists a finite threshold $N_C$ such that policy $\pi$ prioritizes P-opening closed boxes over F-opening them iff the number of closed boxes $n_C > N_C$.} 
From Lemma~\ref{lemma:committing}, we know that once an optimal policy commits to an opening mode for each closed box, the optimal opening sequence is prescribed by the opening thresholds (Algorithm~\ref{algo:committing}). Therefore, P-openings will take place prior to F-openings. 

We proceed by induction on $n_C$. At any state $(1, n_B)$, F-opening is optimal. At the state $(n_C, n_B)$ either P-opening or F-opening is optimal. If we add a closed box to create state $(n_C+1, n_B)$, F-opening could be optimal only if P-opening is not optimal at state $(n_C, n_B)$ (because this would imply that a committing policy F-opens prior to P-opening). 

The finiteness of $N_c$ follows from Lemma~\ref{lemma:infinite_iid_boxes} and the asymptotic optimality of the policy that exclusively P-opens closed boxes. 





\begin{myproof2}{Lemma~\ref{lemma:iid_diff_not_func_of_nb}}



We prove the claim by induction. 
\begin{itemize}
    \item We start from the base case where $n_C=1$. 
Let the closed box be box $i$. 
Following the reasoning of Lemma~\ref{lemma:committing}, the expected payoff of P-opening box $i$ is given by 
\begin{eqnarray*}
   J^{P} ( 1, n_B ) &=& 
   -c^P + \mathbb{E} \brackets{ 
   \max \braces{
   \min \braces{ V_i, \sigma^{F|T_i}}, 
   \max_{j \in \mathcal{P} } \braces{ \min \braces{ V_j, \sigma^{F|B} } } }  }
\end{eqnarray*}

The expected payoff of F-opening box $i$ is given by 
\begin{eqnarray*}
    J^{F}(1, n_B) &=& \E{  \max \braces{ \min \braces{ V_i, \sigma^F }, 
    \max_{j \in \mathcal{P} } \braces{ \min \braces{ V_j, \sigma^{F|B} } }  } }
\end{eqnarray*}

For brevity let $\mathcal{P}(n_B)$ denote the set of $n_B$ bad boxes. 
We let $X(n_B) \defeq \max_{j \in \mathcal{P} (n_B) } \braces{ \min \braces{ V_j, \sigma^{F|B} } }$. 
We note the difference 
\begin{small}
\begin{eqnarray*}
&&  J^{P} ( 1, n_B ) - J^{F}(1, n_B)   \\ 
    &=&  -c^P + \mathbb{E} \brackets{ 
   \max \braces{
   \min \braces{ V_i, \sigma^{F|T_i}}, 
   X }  }  
   -  \E{  \max \braces{ \min \braces{ V_i, \sigma^F }, 
      X } }                       \\ 
    &\overset{(a)}{=}&  -c^P 
    + \pr{  \min \braces{ V_i, \sigma^{F|T_i}} = 0  } 
     \E{ X }  
     +  \pr{  \min \braces{ V_i, \sigma^{F|T_i}} \neq 0  } 
     \E{ \min \braces{ V_i, \sigma^{F|T_i}}  \mid \min \braces{ V_i, \sigma^{F|T_i}} \neq 0}                     \\ 
     && - \pr{  \min \braces{ V_i, \sigma^{F}} = 0  } 
     \E{ X }  
     -  \pr{  \min \braces{ V_i, \sigma^{F}} \neq 0  } 
     \E{ \min \braces{ V_i, \sigma^{F}}  \mid \min \braces{ V_i, \sigma^{F}} \neq 0} \\
     &\overset{(b)}{=}& - c^P + \pr{  \min \braces{ V_i, \sigma^{F|T_i}} \neq 0  } 
     \E{ \min \braces{ V_i, \sigma^{F|T_i}}  \mid \min \braces{ V_i, \sigma^{F|T_i}} \neq 0} \\
     && -   \pr{  \min \braces{ V_i, \sigma^{F}} \neq 0  } 
     \E{ \min \braces{ V_i, \sigma^{F}}  \mid \min \braces{ V_i, \sigma^{F}} \neq 0}  \ , 
\end{eqnarray*}
\end{small}
which is independent of $X$. 
Step (a) follows by noting that $X$ can only take values 0 or $\sigma^{F|B}$, and $\sigma^{F|T_i} \geq \sigma^{F|B}$ almost surely. Hence, conditioned on the event $\braces{\min \braces{ V_i, \sigma^{F|T_i}} \neq 0}$, we have $X \leq \min \braces{ V_i, \sigma^{F|T_i}}$ almost surely.   
Step (b) follows from the simple observation that $\pr{  \min \braces{ V_i, \sigma^{F|T_i}} = 0  } = \pr{  \min \braces{ V_i, \sigma^{F}} = 0  }$. 

\item 
Suppose the induction hypothesis is true for $n_C \geq 1$. 
At state $(n_C+1, n_B)$ where $n_C \geq 1$, the expected payoff of F-opening a closed box and following the optimal policy afterwards is 
\begin{eqnarray*}
    J^{F} (n_C+1,n_B) &=& - c^F + (p^G q^G + p^B q^B ) \cdot 1 
    + \paren{ p^G (1-q^G) + p^B (1-q^B) } \cdot  J(n_C, n_B)  \ . 
\end{eqnarray*}
The expected payoff of P-opening a closed box and following the optimal policy afterwards is 
\begin{eqnarray*}
    J^{P} (n_C+1,n_B) &=&  -c^P 
    + p^G \cdot \paren{ - c^F + q_G \cdot 1 + (1-q_G) \cdot J( n_C, n_B ) }
    + p^B \cdot \paren{ J( n_C, n_B+1 ) } \ , 
\end{eqnarray*}
where we note that an optimal policy F-opens a good box immediately. 
The difference is 
\begin{scriptsize}
\begin{eqnarray}
    J^{F} (n_C+1,n_B) - J^{P} (n_C+1,n_B) &=&  c^P  
    + p^B \cdot \paren{ q^B   - c^F + (1-q^B) J( n_C, n_B ) - J( n_C, n_B+1 ) } \ .  \label{eq:iid_two_types}
\end{eqnarray}
\end{scriptsize}
To prove the lemma, it suffices to show the right-hand-side of above expression is a constant with respect to $n_B$. 



Next, we proceed to show that the term $J(n_C, n_B+1) - (1-q^B) J(n_C, n_B)$ in the above display is indeed independent of $n_B$. 
To this end, we consider how the optimal strategies at state $( n_C, n_B )$ and $( n_C, n_B+1 )$ differ. 
By the induction hypothesis, the decision to whether F-open or P-open a closed box is only a function of $n_C$ and is \textit{independent} of the number of bad type. 
Therefore, the optimal courses of actions starting from state $( n_C, n_B )$ and $( n_C, n_B+1 )$ coincide, up to the moment (if occurs) when the latter has one last bad type and the former has nothing left. 




Let $\cal C(n_C)$ be the set of indices of $n_C$ closed boxes.
For brevity, we denote $J(n_C, 0) = \max_{\pi} ~ \E{ \sum_{i\in {\cal C}(n_C) } \left(  \mathbb{S}_i^{\pi} V_i - \mathbb{F}_i^{\pi}  c_i^F - \mathbb{P}_i^{\pi} c_i^P \right)} $. 
Let $\theta(n) = \paren{ p^G (1-q^G) + p^B (1-q^B) }^n$ be the probability that the optimal policy ends up with no rewards at state $(n, 0)$. 
Further, we recall that the optimal policy will postpone opening the bad boxes to the very end. 
Therefore, we can decompose $J(n_C, n_B)$ and $J(n_C, n_B+1)$ in the following way. 
\begin{eqnarray*}
    J(n_C, n_B) = J(n_C, 0) + \theta(n_C) \E{ X(n_B)} \quad \text{and} \quad 
    J(n_C, n_B+1) = J(n_C, 0) + \theta(n_C) \E{ X(n_B+1)}
\end{eqnarray*}
Hence, we have 
\begin{eqnarray*}
     &&  J(n_C, n_B+1) - (1-q^B) J(n_C, n_B) \\ 
     &=& \theta(n_C) \cdot \paren{ \E{ X(n_B+1)} - (1-q^B)  \E{ X(n_B)} } + q_B J(n_C, 0)  \\
     &=& \theta(n_C) \cdot \paren{ \E{ \max_{j \in \mathcal{P} (n_B+1) } \braces{ \min \braces{ V_j, \sigma^{F|B} } }} - (1-q^B)  \E{ \max_{j \in \mathcal{P} (n_B) } \braces{ \min \braces{ V_j, \sigma^{F|B} } } } }  + q_B J(n_C, 0)  \\ 
     &=& \theta(n_C) \cdot \paren{ q^B \sigma^{F|B} + (1-q^B) \E{ \max_{j \in \mathcal{P} (n_B) } \braces{ \min \braces{ V_j, \sigma^{F|B} } }} - (1-q^B)  \E{ \max_{j \in \mathcal{P} (n_B) } \braces{ \min \braces{ V_j, \sigma^{F|B} } } } } \\ 
     && + q_B J(n_C, 0)  \\
     &=& q^B \cdot \paren{ \theta(n_C)  \sigma^{F|B} +  J(n_C, 0) }   
\end{eqnarray*}
which is independent of $n_B$, as desired. 
\end{itemize}


\end{myproof2}



\subsection{ Optimal policy for PSI-B2I  }
\label{sec:algo_psi_b2i}


% \Yaron{add a definition of OpenBad and briefly connect Algorithm 3 to $N^*_C$}

{  

Algorithm~\ref{algo:psib2i_policy} specifies a class of policies that satisfy the structural properties required by Theorem~\ref{thm:iid_optimal} for PSI-B2I instances. 
It has two parameters $(N_C, \textsc{OpenBad})$, where $N_C$ is the threshold number of closed boxes, above which the policy prioritizes P-opening closed boxes.  
The parameter $\textsc{OpenBad}$ controls whether the policy opens bad-type boxes at all. 


An optimal policy can then be obtained by enumerating this finite class and selecting the best-performing configuration, as described in Algorithm~\ref{algo:psib2i_enum_opt}. 

}

\begin{algorithm}[htbp]
\footnotesize
\caption{Policy template $\pi^{N_C,\textsc{OpenBad}}$ for PSI-B2I.  }
\label{algo:psib2i_policy}
\begin{algorithmic}[1]
\State Initialize counts $(n_C,n_G,n_B,y)\gets (N,0,0,0)$;
\While{$y=0$ and $(n_C+n_G+n_B)>0$}
    \If{$n_G>0$}
        \Comment{Highest priority: F-open good-type boxes}
        \State F-open a good-type box; update $y \gets \max\{y,v\}$; $n_G\gets n_G-1$;
    \ElsIf{$n_C>0$ and $n_C>N_C$}
        \Comment{ P-open closed boxes}
        \State P-open a closed box; $n_C\gets n_C-1$;
        \If{revealed type is good}
            \State $n_G\gets n_G+1$;
        \Else
            \State $n_B\gets n_B+1$;
        \EndIf
    \ElsIf{$n_C>0$ and $n_C\le N_C$}
        % \Comment{Exploitation phase: F-open closed boxes}
        \State F-open a closed box; update $y \gets \max\{y,v\}$; $n_C\gets n_C-1$;
    \Else
        \Comment{Bad-type boxes are lowest priority}
        \If{$\textsc{OpenBad}=\text{True}$ and $n_B>0$}
            \State F-open a bad-type box; update $y \gets \max\{y,v\}$; $n_B\gets n_B-1$;
        \Else
            \State \textbf{break};
        \EndIf
    \EndIf
\EndWhile
\State Select $y$ and stop;
\end{algorithmic}
\end{algorithm}


\begin{algorithm}[htbp]
\footnotesize
\caption{Computing an optimal PSI-B2I policy by enumerating the threshold class (Theorem~\ref{thm:iid_optimal}).}
\label{algo:psib2i_enum_opt}
\begin{algorithmic}[1]
\State Initialize $V^\star \gets -\infty$; $(N_C^\star,\textsc{OpenBad}^\star)\gets (0,\text{False})$;
\For{$N_C \in \{0,1,\ldots,N\}$}
    \For{$\textsc{OpenBad} \in \{\text{False},\text{True}\}$}
        \State Compute $V(N_C,\textsc{OpenBad})$ = expected payoff of policy $\pi^{N_C,\textsc{OpenBad}}$ prescribed by Algorithm~\ref{algo:psib2i_policy}, using Bellman's recursion;
        \If{$V(N_C,\textsc{OpenBad}) > V^\star$}
            \State $V^\star \gets V(N_C,\textsc{OpenBad})$;
            \State $(N_C^\star,\textsc{OpenBad}^\star)\gets (N_C,\textsc{OpenBad})$;
        \EndIf
    \EndFor
\EndFor
\State \Return the policy $\pi^{N_C^\star,\textsc{OpenBad}^\star}$;
\end{algorithmic}
\end{algorithm}




% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================
% ==========================================================================







\section{Proofs of Section~\ref{sec:apx}}

In this section, we present all the proofs for Section~\ref{sec:apx}.
We present the proof of Theorem~\ref{thm:hardness} to the end due to the dependence on other results of which we present the proofs first. 



\subsection{Proof of Lemma \ref{thm:upper_bounds}} \label{appendix:thm:upper_bounds}


The proof of the first inequality mostly follows similar lines of reasoning to that of \cite{brown2013optimal}[Proposition 4.2], and for brevity is thus omitted. 
The remainder of the proof is dedicated to showing that $J^W (\mathcal{C}, \mathcal{P}, y)  \leq  J^K (\mathcal{C}, \mathcal{P}, y)$. 


Define $X^K$ as follows
    $$
    X^K =   \max \left\{ y,  \underset{i \in \mathcal{C}}{ \max }  \left\{ \max \left\{K_i, \widetilde{K}_{i}  \right\} \right\} ,   \underset{i \in \mathcal{P}}{\max}  \left\{ \widetilde{K}_i^{t_i}  \right\} \right\}. 
    $$ 
    Recall from equation~\eqref{eq:sigma_M_C_P} that $\sigma_M =  \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\}$. 
    Since we assume that it is suboptimal to stop in current state $(\mathcal{C}, \mathcal{P}, y)$, we infer that $y<\sigma_M$, and thus, $\sigma_M \geq X^K \geq y \geq 0$. Consequently, we have 
    \begin{eqnarray}
    & & J^K(\mathcal{C}, \mathcal{P}, y) \triangleq \mathbb{E} \left[ X^K \right]  \nonumber \\ 
      &=& \int_{0}^{\sigma_M} \operatorname{Pr} \left[ X^K > s \right] ds   \nonumber \\
       % &=& \int_{0}^{\sigma_M} 1 - \operatorname{Pr} \left[ X^K \leq s \right] ds       \nonumber \\
       &=&  \sigma_M - \int_{y}^{\sigma_M} \operatorname{Pr} \left[ X^K \leq s \right] ds  \nonumber \\
       &=&  \sigma_M - \int_{y}^{\sigma_M}  \left( \prod_{i \in \mathcal{C}} \operatorname{Pr} \left[ \max \left\{K_i, \widetilde{K}_{i}  \right\} \leq s \right] \right) \cdot \left(  \prod_{i \in \mathcal{P}} \operatorname{Pr} \left[ \widetilde{K}_{i}^{t_i} \leq s \mid T_i=t_i \right]  \right)  dy.  \label{eq:proof_bounds_1}  \\ 
       &\geq& \sigma_M - \int_{y}^{\sigma_M}  \prod_{i=1}^{N} \omega_i(x_i , y) dy  \nonumber \\
       &=&  J^W(\mathcal{C}, \mathcal{P}, y). \nonumber 
    \end{eqnarray}
    Equation~\ref{eq:proof_bounds_1} follows from the independence between boxes. The inequality is justified in the remainder of the proof. 
    Recall that, if  $i \in \mathcal{P}$, we have 
\begin{eqnarray*}
  \omega_i(x_i , y) &=& \operatorname{Pr} \left[ \min\{V_i, \sigma_i^{F \mid t_i} \} \leq y \mid T_i=t_i \right]   =  \operatorname{Pr} \left[ \widetilde{K}_i^{t_i} \leq y \mid T_i=t_i \right] .
\end{eqnarray*}
Now, if $i \in \mathcal{C}$, we have 
\begin{eqnarray*}
  \omega_i(x_i , y) &=&  \BFI\{ y > \sigma_i^{F/P}  \} \operatorname{Pr} \left[ \min \left\{ V_i, \sigma_i^{F \mid T_i}, \sigma_i^P \right\} \leq y \right] + \BFI\{ y \leq \sigma_i^{F/P}  \} \operatorname{Pr} \left[  \min \left\{ V_i,  \sigma_i^F \right\} \leq y \right]    \\
  & =& \BFI\{ y > \sigma_i^{F/P}  \} \operatorname{Pr} \left[ \widetilde{K_i} \leq y \right] + \BFI\{ y \leq \sigma_i^{F/P}  \} \operatorname{Pr} \left[  K_i \leq y \right] \\ 
  &=& \operatorname{Pr} \left[ \max \left\{  \BFI\{ y > \sigma_i^{F/P}  \} \widetilde{K_i}  ,  \BFI\{ y \leq \sigma_i^{F/P}  \} K_i \right\}  \leq  y \right]  \\
  &\geq& \operatorname{Pr} \left[ \max \left\{ \widetilde{K_i}, K_i \right\} \leq y \right].
\end{eqnarray*}
 

\subsection{Asymptotic optimality} % Proof of Lemma \ref{lemma:infinite_iid_boxes}}
\label{appendix:ex_infinite_iid_boxes}


\begin{lemma}[Asymptotic optimality]  \label{lemma:infinite_iid_boxes}
Suppose that there exists $\theta>0$ such that $  N_k > \theta  N $ for all $k\in [K]$.
Let $u=\operatorname{Pr} \left[ V_i > \sigma_i^F \right] $, $q = \operatorname{Pr}\left[ \sigma_i^{F \mid T_i} > \sigma_i^P \right]$ and $p = \operatorname{Pr} \left[ V_i > \sigma_i^P \mid  \sigma_i^{F \mid T_i} > \sigma_i^P\right]$, where $i \in [K]$ is the class of boxes that initially attains the largest opening threshold $\sigma_M([N],\emptyset)$. We distinguish between two cases:
% Consider the case of $N$ identical boxes, and
\begin{itemize}
    \item { Case~1: $\sigma_i^F = \sigma_M([N],\emptyset)$.} The policy that always F-opens closed boxes in class $i$ and implements the stopping rule of Theorem~\ref{thm:myopic_stopping} is a factor $(1 - (1-u)^{\theta N})$-close to the optimum.
    \item { Case~2: $\sigma_i^P = \sigma_M([N],\emptyset)$.} The policy that always P-opens closed boxes in class $i$, F-opens partially open boxes when $\sigma_i^{F \mid t_i} > \sigma_i^P$, and implements the stopping rule of Theorem~\ref{thm:myopic_stopping} is a factor $(1 - \left( 1 - p q \right)^{\theta  N })$-close to the optimum.
\end{itemize}
\end{lemma}
The proof is based on the simple observation that the expected profit under the policy described in Cases~1 and~2 asymptotically matches Whittle's integral~\eqref{eq:whittlesintegral}. Intuitively, when we have a sufficiently large number of ``good'' boxes (with associated threshold $\sigma_M({\cal C},{\cal P})$), the actual probability that the effort of opening them is in vain approaches zero, i.e., the gap between Whittle's integral and $\sigma_M({\cal C},{\cal P})$ decreases exponentially in the number of good boxes. Conversely, the policy of Lemma~\ref{lemma:infinite_iid_boxes} has an expected profit approaching $\sigma_M({\cal C},{\cal P})$ from below.



We note in passing, that the Pandora's box model with infinite number of boxes has been commonly used in the literature as a model of consumer search \citep[e.g.,][]{wolinsky1986true}. The fact that our problem admits an asymptotically optimal index policy offers researchers the ability to use the problem as a building block for constructing richer models that capture more realistic behavior.




\begin{myproof}
    

We let $u=\operatorname{Pr} \left[ V_i > \sigma_i^F \right] $, $q = \operatorname{Pr}\left[ \sigma_i^{F \mid T_i} > \sigma_i^P \right]$ and $p = \operatorname{Pr} \left[ V_i > \sigma_i^P \mid  \sigma_i^{F \mid t_i} > \sigma_i^P\right]$, where $i \in [K]$ is the class of boxes that initially attains the largest opening threshold $\sigma_M([N],\emptyset)$.



We first examine Case~1, where $\sigma_i^F = \sigma_M([N], \emptyset)$. In this setting, our policy achieves an expected profit of at least
\begin{eqnarray*}
    & &  -c_i^F  +  u \mathbb{E} \left[ V_i \mid V_i > \sigma_i^F \right] + \left( 1 - u\right)   \left( -c_i^F + u \mathbb{E} \left[ V_i \mid V_i > \sigma_i^F \right] +   \left( 1 - u\right) (...) \right)  \\
    &\geq& u \sigma^F_i + (1-u)u \sigma^F_i + (1-u)^2 u \sigma^F_i + ... + (1-u)^{ \lfloor  \theta \cdot N \rfloor -1} u \sigma^F_i   \\
    &=&  u \sigma^F_i \frac{1-(1-u)^{ \lfloor  \theta \cdot N \rfloor }}{1-(1-u)} \xrightarrow[]{N \rightarrow \infty} \sigma^F_i,
\end{eqnarray*}
where we use the fact
$$
 u \cdot \sigma_i^F = - c_i^F + u \cdot \mathbb{E} \left[ V_i \mid V_i > \sigma_i^F \right].
$$
By Lemma~\ref{thm:upper_bounds}, we know that $\sigma_i^F$ is an upper bound on the optimal expected profit. Hence, we derive the approximation ratio stated in Lemma~\ref{lemma:infinite_iid_boxes}.


Next, we examine Case~2, where $\sigma_i^P = \sigma_M([N], \emptyset)$. Here, our policy achieves an expected profit of at least
\begin{eqnarray*}
  & &  -c_i^P  + q \left( -c_i^F +  p \mathbb{E}\left[ V_i \mid V_i > \sigma_i^P, \sigma_i^{F \mid T_i} > \sigma_i^P \right]  \right)  \\
   &+&  \left( 1-q + q(1-p) \right) \left( -c_i^P  + q \left( -c_i^F +  p \mathbb{E}\left[ V_i \mid V_i > \sigma_i^P, \sigma_i^{F \mid T_i} > \sigma_i^P \right] + \left( 1-q + q(1-p) \right) \left( ... \right) \right)  \right)  \\
   &\geq & pq \sigma^P_i + (1-pq) pq\sigma^P_i + (1-pq)^2pq \sigma^P_i + ...  + (1-pq)^{\lfloor  \theta \cdot N \rfloor-1} pq \sigma^P_i \\
    &=& pq \sigma^P_i \frac{1-(1-pq)^{\lfloor  \theta \cdot N \rfloor }}{1-(1-pq)} \xrightarrow[]{N \rightarrow \infty} \sigma^P_i  ,
\end{eqnarray*}
where we use the fact 
$$
p_{} q_{} \sigma_i^P = -c_i^P + q_{} \left( -c_i^F +  p_{} \mathbb{E}\left[ V_i  \mid V_i > \sigma_i^P, \sigma_i^{F \mid T_i} > \sigma_i^P \right]  \right).
$$
By Lemma~\ref{thm:upper_bounds}, we know that $\sigma_i^P$ is an upper bound on the optimal expected profit. 
Hence, the approximation ratio of Lemma~\ref{lemma:infinite_iid_boxes} immediately follows. %  and note $\alpha(N) = 1-(1-pq)^{\theta \cdot N}$.
% \Halmos
\end{myproof}





\subsection{Proof of Lemma \ref{lemma:committing} }
\label{appendix:lemma:committing}

First, we identify necessary and sufficient conditions such that there is no gap between the free-info upper bound and the value function.

\begin{lemma}
% [Non-exposed policies]  
\label{lemma:non-exposed_policy}
For every policy $\pi$, we have $J^{\pi,K}(s_0) = J^{\pi}(s_0)$ if and only if policy $\pi$ satisfies the following conditions:
\begin{enumerate}
  \item $\pi$ selects any F-opened box $i$ (which was not P-opened) whose value satisfies $V_i > \sigma^{F}_i$;
  \item $\pi$ fully opens any P-opened box $i$ whose type satisfies $\sigma^{F \mid T_i}_i > \sigma^{P}_i$;
  \item $\pi$ selects any F-opened box $i$ (which was already P-opened) that satisfies $V_i > \min \{\sigma^{P}_i, \sigma^{F \mid T_i}_i \}$.
\end{enumerate}
\end{lemma}

Consistently with the terminology used in previous literature, we call these policies {\em non-exposed}. 
Note that non-exposed policies were introduced by \cite{beyhaghi2019pandora}. Our proof of Lemma~\ref{lemma:non-exposed_policy} in Appendix~\ref{appendix:lemma:non-exposed_policy} requires a slightly more general argument for our sequential inspection processes and the corresponding two-stage (rather than single-stage) call options.

Now, using equation~\eqref{eq:free}, for any committing policy $\pi^{F,P}$, the expected profit in the free-info problem is
\begin{eqnarray}
J^{\pi, K}(s_0) &=& \E{   
\sum_{i=1}^{N} \left(  \mathbb{S}_i^{\pi} K_i (1-\indPi) + \widetilde{\mathbb{S}}_i^{\pi} \widetilde{K}^{t_i}_i \indPi  \right) 
} \nonumber \\
% u_{\rm{II}}(\pi^{F,P})  &=& \mathbb{E} \Big[ \sum_{i=1}^{N} \indSi^{} K_i(1-\indPi^{ } )+\indSitilde^{ } \widetilde{K}_i \indPi^{ }    \Big]  \nonumber \\
&=& \mathbb{E} \Big[ \sum_{i\in F} \indSi^{ } K_i(1-\indPi^{ } )+\sum_{i\in P}\indSitilde^{ } \widetilde{K}_i \indPi^{ }    \Big]  \nonumber \\ 
&\leq&  \mathbb{E}\left[ \max \left\{ \underset{i \in F}{\max} \{  K_i\}   , \underset{i \in P}{\max}  \{ \widetilde{K}_i \}  \right\}\right] \nonumber, 
\end{eqnarray}
where the first equality holds due to the construction of the committing policy $\pi^{F,P}$, and the inequality follows from the constraints 
$\sum_{i=1}^{N}  \indSi^{\pi} + \sum_{i=1}^{N}\indSitilde^{\pi}  \leq 1 $, and $0 \leq \indPi^{\pi} \leq 1 $.


To conclude the proof, it suffices to show that this upper bound is matched by $\pi^{F,P}$ in the real-world problem. 
To see this, we first remark that the committing policy $\pi^{F,P}$ is non-exposed, and thus, by Lemma~\ref{lemma:non-exposed_policy}, $J^{\pi^{F,P} } (s_0) =J^{\pi^{F,P} , M }(s_0)  $.
Therefore, to prove the lemma, it suffices to show that in the free-info problem, policy $\pi^{F,P}$ achieves the maximal capped realization. 
Letting $\widehat{K_i} = K_i $ if $i \in F$ and $\widehat{K_i} = \widetilde{K_i}$ if $i \in P$ be the capped value of each box $i$, we would like to show that that policy $\pi^{F,P}$ selects $\underset{i \in [N]}{\max} \left\{ \widehat{K}_i \right\}$ under any realization. 
%That is, whenever the policy stops, it always selects the box with the largest capped value. 

Let $j$ denote the box selected by the policy. 
We note that, at termination, except for $\widehat{K}_j$, there are two groups of boxes: (1) boxes that were F-opened (perhaps after P-opening) ; and (2) boxes that were not F-opened (but possibly were P-opened).
We argue that the capped value of each box in both groups is smaller than or equal to $\widehat{K}_j$. 

Specifically, for any box $i$ in group 1, observe that  
\begin{itemize}
    \item Fact 1: $V_i \leq V_j$. This is due to the fact that policy $\pi^{F,P}$ always selects the best prize so far, and thus $V_i \leq V_j$;
    \item Fact 2: $V_i < \sigma_j$. To see this, note that if $V_j \geq \sigma_j$ the policy immediately stops after F-opening box $j$. In this case, $V_i \leq \sigma_j$ (otherwise box $j$ would not have been opened). Alternatively, if $V_j<\sigma_j$, then it follows from fact 1 that $V_i<\sigma_j$. 
\end{itemize}
Recalling that $\widehat{K_i} \leq V_i$, we have $\widehat{K_j} \geq \widehat{K_i}$ for any box $i$ in group (1). 

Next, for any box $i$ in group (2), we observe that 
\begin{itemize}
    \item Fact 3: $\sigma_j \geq \sigma_i \geq \widehat{K_i}$, since  policy $\pi^{F,P}$ always opens the box with largest threshold;
    \item Fact 4: $V_j \geq \sigma_i \geq \widehat{K_i}$, since  policy $\pi^{F,P}$ obeys the optimal stopping rule. 
\end{itemize}
Hence, $\widehat{K}_j$ is indeed the largest capped value. 
It then follows that policy $\pi^{F,P}$ attains the largest capped realization.
% \Halmos



\subsection{Proof of Lemma~\ref{lemma:non-exposed_policy}}
\label{appendix:lemma:non-exposed_policy}

Recall the expressions of $J^\pi(s_0)$ and $J^{\pi, K}(s_0)$
$$
J^\pi(s_0) =  \E{   
\sum_{i=1}^{N} \left(  \mathbb{S}_i^{\pi} V_i - \mathbb{F}_i^{\pi}  c_i^F - \mathbb{P}_i^{\pi} c_i^P \right) + \sum_{i=1}^{N} \left(  \widetilde{\mathbb{S}}_i^{\pi} V_i -  \widetilde{\mathbb{F}}_i^{\pi}  c_i^F \right) 
} \ , 
$$
and 
$$
J^{\pi, K}(s_0) = \E{   
\sum_{i=1}^{N} \left(  \mathbb{S}_i^{\pi} K_i (1-\indPi) + \widetilde{\mathbb{S}}_i^{\pi} \widetilde{K}^{t_i}_i \indPi  \right) 
} \ . 
$$
To prove the lemma\footnote{For brevity, we mute the superscripts of $\mathbb{S}_i^{\pi}, \widetilde{\mathbb{S}}_i^{\pi}, \indFi^{\pi}, \indFitilde^{\pi}, \indPi^{\pi}$ below in this proof. }, it suffices to show that for all $i$,
$$
\mathbb{E}\big[\indSi  V_i + \indSitilde V_i - \indFi c_i^F - \indFitilde c_i^F - \indPi c_i^P \big]  
\leq \mathbb{E}[\indSi K_i(1-\indPi)+\indSitilde \widetilde{K}_i \indPi] \ ,
$$
and that the inequalities hold with equalities if and only if the policy satisfies the three criteria for all boxes $i$. 
We proceed to show that this is indeed true. 

For any box $i \in [N]$, its contribution to the total expected profit is 
\begin{eqnarray*}
\underbrace{\mathbb{E}\big[ \indSi  V_i - \indFi c_i^F \big]}_{\textcircled{1}} + \underbrace{\mathbb{E}\big[ \indSitilde V_i  - \indFitilde c_i^F - \indPi c_i^P \big]}_{\textcircled{2}} \ ,
\end{eqnarray*}
where the term \textcircled{1} corresponds to the expected profit from box $i$ by directly F-opening it, while the term \textcircled{2} corresponds to a P-opening followed by a F-opening. We derive upper bounds on each of two terms, and show these bounds are exactly tight for a non-exposed policy. 

\paragraph{The first condition of non-exposed policies.} For the first term, we note that 
\begin{eqnarray}
  \textcircled{1} &=& \mathbb{E}\big[\indSi  V_i - \indFi c_i^F \mid \indPi=0 \big] \operatorname{Pr}[\indPi=0]  + \mathbb{E}\big[ \underbrace{\indSi  V_i - \indFi c_i^F }_{=0} \mid \indPi=1 \big]  \operatorname{Pr}[\indPi=1]  \label{eq:expiredBox_1_1} \\
  &=& \mathbb{E}\left[ \indSi V_i - \indFi  \mathbb{E}[(V_i-\sigma_i^F)^+ ] \mid \indPi=0\right] \operatorname{Pr}[\indPi=0]  \label{eq:lemma_proof_expired_box_1} \\
   &=& \mathbb{E}\left[ \indSi V_i - \indFi  (V_i-\sigma_i^F)^+  \mid \indPi=0\right]  \operatorname{Pr}[\indPi=0] \label{eq:lemma_proof_expired_box_2} \\
   &\leq&  \mathbb{E}\left[ \indSi V_i - \indSi  (V_i-\sigma_i^F)^+  \mid \indPi=0\right] \operatorname{Pr}[\indPi=0] \label{eq:lemma_proof_expired_box_3} \\
   &=& \mathbb{E}\left[ \indSi K_i  \mid \indPi=0\right] \operatorname{Pr}[\indPi=0]  \label{eq:lemma_proof_expired_box_3_2},
\end{eqnarray}
where equation~\eqref{eq:expiredBox_1_1} is obtained by conditioning on the decision to P-open, and by showing that the underbraced expression is equal to zero. 
The latter fact follows  by noting that $\indSi \leq \indFi = 1 - \indPi=0$ when $\indPi= 1 $.
Equation~\eqref{eq:lemma_proof_expired_box_1} follows from  the definition of the F-threshold $\sigma_i^F$, and equation~\eqref{eq:lemma_proof_expired_box_2} is due to the independence of $\indFi$ and $V_i$, since the decision of directly F-opening or not does not depend on the realization of $V_i$. The inequality again proceeds from constraint $\indSi \leq \indFi$. 
We observe that this inequality is tight if and only if $\mathbb{E}\left[ (\indFi-\indSi) (V_i-\sigma_i^F)^+ \mid \indPi=0 \right] = 0 $. 
In particular, when $V_i \leq \sigma^{F}_i$, this inequality is satisfied with equality.
Moreover, when $V_i$ satisfies $V_i > \sigma^{F}_i$, the first criterion in the definition of non-exposed policies is a sufficient and necessary condition for the box to be selected, in which case $\indSi=\indFi=1$ and the above inequality is satisfied with equality.
Finally, equation~\eqref{eq:lemma_proof_expired_box_3_2} immediately follows from the definition of $K_i$.
We mention in passing that our analysis of term \textcircled{1} is nearly identical to that of \cite{kleinberg2016descending}[Lemma 1].
\paragraph{The second condition of non-exposed policies.}
Now, let us turn to the second term:
\begin{scriptsize}
\begin{eqnarray}
 \textcircled{2}  &=&  \mathbb{E}\left[ \indSitilde V_i  - \indFitilde c_i^F - \indPi c_i^P \mid \indPi=1\right]  \operatorname{Pr}[\indPi=1] +  \mathbb{E}\left[  \underbrace{\indSitilde V_i  - \indFitilde c_i^F - \indPi c_i^P }_{=0} \mid \indPi=0\right]  \operatorname{Pr}[\indPi=0]  \label{eq:expiredBox_2_1} \\
 % &=& \mathbb{E}\left[ \indSitilde V_i  - \indFitilde c_i^F - \indPi c_i^P \mid \indPi=1\right]  \operatorname{Pr}[\indPi=1]    \label{eq:expiredBox_2_2}  \\
   &=&   \mathbb{E}\left[ \indSitilde V_i  - \indFitilde c_i^F - \indPi \mathbb{E}\big[\max\{0, -c_i^F+\mathbb{E}[ (V_i-\sigma_i^P)^+  \mid T_i]\}\big] \mid  \indPi=1 \right]\operatorname{Pr}[\indPi=1]   \label{eq:lemma_proof_expired_box_4}  \\
   &=&  \mathbb{E}\left[ \indSitilde V_i  - \indFitilde c_i^F - \indPi \max\{0, -c_i^F+\mathbb{E}\big[ (V_i-\sigma_i^P)^+  \mid T_i \big]\} \mid \indPi=1 \right] \operatorname{Pr}[\indPi=1] \label{eq:lemma_proof_expired_box_5} \\
   &\leq&  \mathbb{E}\left[ \indSitilde V_i  - \indFitilde c_i^F - \indFitilde \max\{0, -c_i^F+\mathbb{E}\big[ (V_i-\sigma_i^P)^+  \mid T_i\big]\} \mid \indPi=1 \right]  \operatorname{Pr}[\indPi=1] \label{eq:lemma_proof_expired_box_6},
\end{eqnarray}
\end{scriptsize}
where equation~\eqref{eq:expiredBox_2_1} is obtained by conditioning on the decision to P-open, and the underbraced term is equal to zero when $\indPi=0$ (this fact can be verified from the definition of 
$\indSitilde$ and $\indFitilde$).
Equation~\eqref{eq:lemma_proof_expired_box_4} is due to definition of the P-threshold $\sigma^{P}_i$.
Equation \eqref{eq:lemma_proof_expired_box_5} is due to the independence of $\indPi$ and $T_i$, since the decision to partially open does not depend on the realization of the type $T_i$. 
The inequality \eqref{eq:lemma_proof_expired_box_6} holds since $\indFitilde \leq \indPi$. 
 

 
 We next examine when the inequality~\ref{eq:lemma_proof_expired_box_6} is tight. To this end, let $ \varphi_i(t_i)=\max \left \{0, -c_i^F+\mathbb{E}[ (V_i-\sigma_i^P)^+  \mid T_i = t_i] \right \} $. We can write the difference between equations \eqref{eq:lemma_proof_expired_box_6} and \eqref{eq:lemma_proof_expired_box_5} as follows:
\begin{eqnarray}
  & & \eqref{eq:lemma_proof_expired_box_6}-\eqref{eq:lemma_proof_expired_box_5} \nonumber\\
  &=& \mathbb{E}\left[ \left(\indPi - \indFitilde\right)\varphi(T_i) \mid \indPi=1 \right] \operatorname{Pr}[\indPi=1]   \label{eq:expiredBox_3_1} \\
   &=& \sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i=t_i]  \BFI\{ \varphi(t_i)=0 \} \operatorname{Pr}[\indPi=1]  \cdot 0  \label{eq:expiredBox_3_2} \\
   &+&  \sum_{t_i \in \Gamma_i}  \operatorname{Pr}[T_i=t_i] \BFI\{ \varphi(t_i)>0 \}  \operatorname{Pr}[\indPi=1] \operatorname{Pr}\Big[\indFitilde=1\mid \indPi=1, T_i=t_i   \Big]  \cdot 0   \label{eq:expiredBox_3_3} \\
   &+&  \sum_{t_i \in \Gamma_i}  \operatorname{Pr}[T_i=t_i] \BFI\{ \varphi(t_i)>0 \}  \operatorname{Pr}[\indPi=1] \operatorname{Pr}\Big[\indFitilde=0\mid \indPi=1, T_i=t_i  \Big] \cdot \underbrace{  \varphi_i(t_i) }_{>0} \label{eq:expiredBox_3_4},
\end{eqnarray}
In equation \eqref{eq:expiredBox_3_1}, we substitute the function $\varphi_i(t_i)$ into the difference between \eqref{eq:lemma_proof_expired_box_6} and \eqref{eq:lemma_proof_expired_box_5}. 
We then decompose the expectation into three summations based on the type $t_i$.
Specifically, expression \eqref{eq:expiredBox_3_2} corresponds to the ``bad'' types $t_i$, for which F-opening is not worthwhile. 
Expression \eqref{eq:expiredBox_3_3} corresponds to the case where box $i$ is F-opened ($\indFitilde=1$) after being P-opened ($\indPi=1$).
Finally, expression \eqref{eq:expiredBox_3_4} corresponds to the case where box $i$ is P-opened ($\indPi=1$) but not F-opened ($\indFitilde=0$).
Therefore, equations  $\eqref{eq:lemma_proof_expired_box_6}$ and $\eqref{eq:lemma_proof_expired_box_5}$ are equal if and only if $\varphi_i(t_i)>0 $ implies that $\operatorname{Pr} \left[ \indFitilde=0  ~\middle \vert~ \indPi=1, T_i=t_i  \right]=0$. Recall that $c_i^F = \mathbb{E}_{V_i \mid T_i=t_i}\Big[(V_i - \sigma^{F \mid t_i}_i)^+\Big]$ by definition of $\sigma^{F \mid t_i}_i$, and that $ \varphi_i(t_i)=\max \left \{0, -c_i^F+\mathbb{E} \left [ (V_i-\sigma_i^P)^+  \mid T_i = t_i \right] \right\} $.
Therefore, we have 
\begin{eqnarray}
 \varphi_i(t_i)>0  & \Leftrightarrow & -c_i^F+\mathbb{E}[ (V_i-\sigma_i^P)^+  \mid T_i = t_i]>0  \nonumber \\ 
 & \Leftrightarrow & \mathbb{E}[ (V_i-\sigma_i^P)^+  \mid T_i = t_i] > c_i^F \nonumber \\ 
 & \Leftrightarrow & \mathbb{E}_{V_i \mid T_i=t_i}\Big[(V_i - \sigma^{P}_i)^+\Big] > \mathbb{E}_{V_i \mid T_i=t_i}\Big[(V_i - \sigma^{F \mid t_i}_i)^+\Big] \nonumber \\
 & \Leftrightarrow & \sigma_i^{F \mid t_i} > \sigma_i^{P}.\nonumber
\end{eqnarray}
This is exactly the second criterion in the definition of non-exposed policies, which requires that if $\sigma_i^{F \mid t_i} > \sigma_i^{P}$ then F-opening will succeed a P-opening.
\\
\paragraph{The third condition of non-exposed policies.} Now we get back to characterizing an upper bound on term \textcircled{2}:
\begin{scriptsize}
\begin{eqnarray}
   &&  \mathbb{E}\left[ \indSitilde V_i  - \indFitilde \left( c_i^F + \max\{0, -c_i^F+\mathbb{E}[ (V_i-\sigma_i^P)^+  \mid T_i]\} \right) \mid \indPi=1 \right]  \operatorname{Pr}[\indPi=1] \nonumber   \\
   &=&  \mathbb{E}\left[ \indSitilde V_i  - \indFitilde \left( \max\{c_i^F, \mathbb{E}[ (V_i-\sigma_i^P)^+  \mid T_i]\} \right) \mid \indPi = 1\right]   \operatorname{Pr}[\indPi=1]     \nonumber  \\
   &=&  \sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i = t_i]  \BFI\{ c_i^F \geq \mathbb{E}\left[(V_i-\sigma_i^P)^+ \mid T_i=t_i\right] \}  \mathbb{E}  \left[ \indSitilde V_i  -  \indFitilde c_i^F  \mid T_i=t_i, \indPi = 1 \right]\operatorname{Pr}[\indPi=1]      \nonumber     \\
   &+&  \sum_{t_i \in \Gamma_i}   \operatorname{Pr}[T_i = t_i]  \BFI\{  c_i^F < \mathbb{E}\left[(V_i-\sigma_i^P)^+ \mid T_i=t_i\right] \}   \mathbb{E} \left[ \indSitilde V_i  -  \indFitilde \mathbb{E}\left[(V_i-\sigma_i^P)^+ \mid T_i=t_i\right] \mid T_i=t_i, \indPi = 1 \right]\operatorname{Pr}[\indPi=1]     \label{eq:expiredBox_4_1}     \\
   &=& \sum_{t_i \in \Gamma_i}  \operatorname{Pr}[T_i = t_i]  \BFI\{ c_i^F \geq \mathbb{E}\left[(V_i-\sigma_i^P)^+ \mid T_i=t_i\right] \}  \mathbb{E}  \left[ \indSitilde V_i  -  \indFitilde \mathbb{E}\left[(V_i - \sigma_i^{F \mid t_i})^+ \mid T_i=t_i \right]  \mid T_i=t_i, \indPi = 1 \right] \operatorname{Pr}[\indPi=1]   \nonumber     \\
   &+&  \sum_{t_i \in \Gamma_i}  \operatorname{Pr}[T_i = t_i]  \BFI\{  c_i^F < \mathbb{E}\left[(V_i-\sigma_i^P)^+ \mid T_i=t_i \right] \}  \mathbb{E} \left[ \indSitilde V_i  -  \indFitilde \mathbb{E}\left[(V_i-\sigma_i^P)^+ \mid T_i=t_i\right] \mid T_i=t_i, \indPi = 1 \right] \operatorname{Pr}[\indPi=1]    \label{eq:expiredBox_4_2} \\
   &=&     \sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i = t_i]  \BFI\{ c_i^F \geq \mathbb{E}\left[(V_i-\sigma_i^P)^+ \mid T_i= t_i\right] \}  \mathbb{E}  \left[ \indSitilde V_i  -  \indFitilde (V_i - \sigma_i^{F \mid t_i})^+  \mid T_i = t_i , \indPi=1 \right]  \operatorname{Pr}[\indPi=1]   \nonumber    \\
   &+&  \sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i = t_i]  \BFI\{  c_i^F < \mathbb{E}\left[(V_i-\sigma_i^P)^+  \mid T_i =  t_i \right] \} \mathbb{E} \left[ \indSitilde V_i  -  \indFitilde (V_i-\sigma_i^P)^+   \mid T_i =  t_i, \indPi=1 \right]  \operatorname{Pr}[\indPi=1]   \label{eq:lemma_proof_expired_box_7a}   
\end{eqnarray}
\end{scriptsize}
The first equation is identical to equation~\eqref{eq:lemma_proof_expired_box_6}.
Equation~\eqref{eq:expiredBox_4_1} is obtained by conditioning on the type $t_i$ revealed after P-opening box $i$. 
Equation~\eqref{eq:expiredBox_4_2} is derived by substituting the definition of $\sigma^{F \mid t_i}_i$ (cf. Definition~\ref{def:testing_threshold}). 
We obtain equation\eqref{eq:lemma_proof_expired_box_7a} by consolidating the expectation operator around
$(V_i-\sigma_i^P)^+$ and $(V_i - \sigma_i^{F \mid t_i})^+$ and by observing the following sequence of equalities: 
\begin{eqnarray}
  &&\mathbb{E}\left[ \indFitilde \mathbb{E}\left[(V_i-\sigma_i^{F \mid t_i})^+ \mid T_i=t_i \right] \mid T_i=t_i, \indPi=1 \right] \nonumber\\
  &=& %\mathbb{E}\left[ \indFitilde \mathbb{E}\left[(V_i-\sigma_i^{F \mid t_i})^+  \mid T_i=t_i, \indPi=1  \right] \mid T_i=t_i, \indPi=1 \right]   \label{eq:independence_1_1}\\
   %&=& 
   \mathbb{E}\left[ \indFitilde  \mid T_i=t_i, \indPi=1 \right] \mathbb{E}\left[(V_i-\sigma_i^{F \mid t_i})^+  \mid T_i=t_i, \indPi=1  \right] \label{eq:independence_1_2}  \nonumber \\
   &=& \mathbb{E}\left[ \indFitilde (V_i-\sigma_i^{F \mid t_i})^+  \mid T_i=t_i, \indPi=1 \right] \label{eq:independence_1_3}. \nonumber 
\end{eqnarray}
The first equality follows from the fact that $\mathbb{E}\left[(V_i-\sigma_i^{F \mid t_i})^+ ~\middle \vert ~ T_i=t_i \right] $ is a constant, independent of $\indFitilde$. The second equality follows from the independence between $\indFitilde$ and $V_i$ conditional on $T_i=t_i$.
\iffalse
    where \eqref{eq:independence_1_1} is by iterated conditioning (on what is known), \eqref{eq:independence_1_2} is by taking out what is known, and \eqref{eq:independence_1_3} is by independence discussed above. By the same reasoning, we have
    \begin{equation}\label{eq:independence_1_4}
         \mathbb{E}\left[ \indFitilde \mathbb{E}\left[(V_i-\sigma_i^P)^+ \right] \mid T_i=t_i, \indPi=1 \right] = \mathbb{E}\left[ \indFitilde (V_i-\sigma_i^P)^+  \mid T_i=t_i, \indPi=1  \right].
    \end{equation}
\fi
Moving forward, we have:
\begin{scriptsize}
\begin{eqnarray}
\eqref{eq:lemma_proof_expired_box_7a} 
&=& \sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i = t_i]  \BFI\{ c_i^F \geq \mathbb{E}\left[(V_i-\sigma_i^P)^+ \mid T_i= t_i\right] \}  \mathbb{E}  \left[ \indSitilde V_i  -  \indFitilde (V_i - \sigma_i^{F \mid t_i})^+  \mid T_i = t_i , \indPi=1 \right]  \operatorname{Pr}[\indPi=1]   \nonumber    \\
   &+&  \sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i = t_i]  \BFI\{  c_i^F < \mathbb{E}\left[(V_i-\sigma_i^P)^+  \mid T_i =  t_i \right] \} \mathbb{E} \left[ \indSitilde V_i  -  \indFitilde (V_i-\sigma_i^P)^+   \mid T_i =  t_i, \indPi=1 \right]  \operatorname{Pr}[\indPi=1]   \label{eq:lemma_proof_expired_box_7}   \\
   &\leq&\sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i = t_i]  \BFI\{ c_i^F \geq \mathbb{E}\left[(V_i-\sigma_i^P)^+  \mid T_i= t_i\right] \}  \mathbb{E}  \left[ \indSitilde V_i  -  \indSitilde (V_i - \sigma_i^{F \mid t_i})^+  \mid T_i = t_i, \indPi=1 \right] \operatorname{Pr}[\indPi=1]    \nonumber     \\
   &+& \sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i = t_i]  \BFI\{  c_i^F < \mathbb{E}\left[(V_i-\sigma_i^P)^+  \mid T_i= t_i \right] \} \mathbb{E} \left[ \indSitilde V_i  -  \indSitilde (V_i-\sigma_i^P)^+   \mid T_i =  t_i , \indPi=1 \right] \operatorname{Pr}[\indPi=1]  \label{eq:lemma_proof_expired_box_8}     \\
   &=&\sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i = t_i]  \BFI\{ \sigma_i^{F \mid t_i} \leq \sigma_i^P \}  \mathbb{E}  \left[ \indSitilde V_i  -  \indSitilde (V_i - \sigma_i^{F \mid t_i})^+  \mid T_i = t_i, \indPi=1\right] \operatorname{Pr}[\indPi=1]    \nonumber     \\
   &+& \sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i = t_i]  \BFI\{  \sigma_i^{F \mid t_i} > \sigma_i^P \} \mathbb{E} \left[ \indSitilde V_i  -  \indSitilde (V_i-\sigma_i^P)^+  \mid T_i = t_i , \indPi=1\right] \operatorname{Pr}[\indPi=1]  \label{eq:lemma_proof_expired_box_9}  \\
   &=& \sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i = t_i]  \BFI\{ \sigma_i^{F \mid t_i} \leq \sigma_i^P \}  \mathbb{E}  \left[ \indSitilde \min\{ V_i, \sigma_i^{F \mid t_i}\}  \mid T_i = t_i, \indPi=1\right] \operatorname{Pr}[\indPi=1]    \nonumber     \\
   &+& \sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i = t_i]  \BFI\{  \sigma_i^{F \mid t_i} > \sigma_i^P \} \mathbb{E} \left[ \indSitilde \min\{ V_i, \sigma_i^P\}  \mid T_i = t_i, \indPi=1 \right] \operatorname{Pr}[\indPi=1]   \label{eq:lemma_proof_expired_box_10}   \\
   &=& \mathbb{E}\Big[\indSitilde \min\{V_i, \sigma_i^P, \sigma^{F \mid T_i}_i \} \mid \indPi=1 \Big] \operatorname{Pr}[\indPi=1]  \label{eq:lemma_proof_expired_box_11}    \\
   &=&  \mathbb{E}[\indSitilde \widetilde{K}_i \mid \indPi=1] \operatorname{Pr}[\indPi=1] \label{eq:lemma_proof_expired_box_12}.
\end{eqnarray}
\end{scriptsize}
The first equation is identical to equation~\ref{eq:lemma_proof_expired_box_7a}. The inequality~\ref{eq:lemma_proof_expired_box_8} follows from the inequality $ \indSitilde  \leq \indFitilde $. 
For equation\eqref{eq:lemma_proof_expired_box_9}, note that by definition of $\sigma^{F \mid t_i}_i$, 
\begin{eqnarray}
 c_i^F \geq \mathbb{E}\left[(V_i-\sigma_i^P)^+ \mid T_i=t_i\right] &\Leftrightarrow& \mathbb{E}\left[(V_i-\sigma_i^{F \mid t_i})^+  \mid T_i=t_i\right] \geq \mathbb{E}\left[(V_i-\sigma_i^P)^+ \mid T_i=t_i\right] \nonumber\\
 &\Leftrightarrow& \sigma_i^{F \mid t_i} \leq \sigma_i^P,\nonumber
\end{eqnarray}
where the last equivalence follows from the monotonicity of the mapping $x \rightarrow  \E{ (V_i-x)^+ \mid T_i=t_i }  $. % shown in Lemma \ref{lemma:monotonicity_existence}. 
Equation~\eqref{eq:lemma_proof_expired_box_10} follows from the identity $x-(x-y)^+=\min\{x,y \}$. 
Equation~\eqref{eq:lemma_proof_expired_box_11} can be justified  by conditioning on $T_i$, and finally, equation\eqref{eq:lemma_proof_expired_box_12} follows from the definition of $\widetilde{K}_i$. 

To identify under which condition we have $\eqref{eq:lemma_proof_expired_box_7} = \eqref{eq:lemma_proof_expired_box_8}$, we consider the difference between these terms:
\begin{eqnarray}
  \eqref{eq:lemma_proof_expired_box_8}-\eqref{eq:lemma_proof_expired_box_7} &=&  \sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i = t_i]  \BFI\{ \sigma_i^{F \mid t_i} \leq \sigma_i^P \}  \mathbb{E}  \left[(\indFitilde-\indSitilde) (V_i - \sigma_i^{F \mid t_i})^+  \mid T_i = t_i\right] \operatorname{Pr}[\indPi=1]    \nonumber     \\
   &+& \sum_{t_i \in \Gamma_i} \operatorname{Pr}[T_i = t_i]  \BFI\{  \sigma_i^{F \mid t_i} > \sigma_i^P \} \mathbb{E} \left[ (\indFitilde-\indSitilde) (V_i-\sigma_i^P)^+  \mid T_i = t_i \right] \operatorname{Pr}[\indPi=1].\nonumber
\end{eqnarray}
We note that the latter sum-expressions are equal to zero if and only if the policy $\pi$ is designed such that 
\begin{itemize}
    \item   $  \left\{ V_i > \sigma_i^{F \mid t_i} \right\}  \cap \left\{  \sigma_i^{F \mid t_i} \leq \sigma_i^P \right\}  \cap \left\{ \indFitilde=1 \right\} \Rightarrow \left\{  \indSitilde=1 \right\}$ , and
    \item   $  \left \{ V_i > \sigma_i^P \right\} \cap  \left \{  \sigma_i^{F \mid t_i} > \sigma_i^P \right\}  \cap  \left\{  \indFitilde=1 \right\} \Rightarrow \left\{ \indSitilde=1 \right\} $.
\end{itemize}
The latter conditions can be reformulated as $ \left\{ V_i > \min \{\sigma_i^P, \sigma_i^{F \mid t_i} \} \right\} \cap  \left\{ \indFitilde=1 \right\} \Rightarrow \left\{ \indSitilde=1 \right\} $. 
This is precisely the third criterion in the definition of non-exposed policies.

Finally, combining inequalities \eqref{eq:lemma_proof_expired_box_3_2} and \eqref{eq:lemma_proof_expired_box_12} yields that the expected profit from box $i$ is bounded above by:
\begin{eqnarray}
   \mathbb{E}\big[\indSi  V_i + \indSitilde V_i - \indFi c_i^F - \indFitilde c_i^F - \indPi c_i^P \big] &\leq &   \mathbb{E}\left[ \indSi K_i \mid \indPi=0 \right] \operatorname{Pr}[\indPi=0] + \mathbb{E}[\indSitilde \widetilde{K}_i \mid \indPi=1] \operatorname{Pr}[\indPi=1] \nonumber \\
   &=& \mathbb{E}[\indSi K_i(1-\indPi)+\indSitilde \widetilde{K}_i \indPi] \ .  \nonumber
\end{eqnarray}
Following from the discussion above, we know that the inequalities hold as equalities for all $i$ if and only if the policy is non-exposed.






\subsection{Proof of Theorem~\ref{thm:1-1/e}} \label{appendix:thm:1-1/e}
In the spirit of \cite{beyhaghi2019pandora}, we cast our free-info problem into a respective stochastic submodular optimization problem. 
The adaptivity gap result by \cite{asadpour2015maximizing}  guarantees that the performance of some committing policy is comparable to a fully adaptive policy, up to a constant-factor approximation.


The proof is organized as follows.
We begin by summarizing results from \cite{asadpour2015maximizing} on stochastic monotone submodular optimization, in section~\ref{subsec:summary_submodular}. In section~\ref{subsec:submodular_problems}, we then formulate specific submodular optimization problems related to our Pandora's box with sequential inspection. In section~\ref{subsec:submodular_transformation}, we continue to define the transformation of policies between the free-info problem and the submodular problem and prove relations between these transformations. Finally, in section~\ref{subsec:proof_of_thm:1-1/e}, we combine earlier results to prove the main theorem.

\subsubsection{Submodular monotone nonnegative maximization subject to a matroid constraint.} \label{subsec:summary_submodular}
We consider the class of stochastic optimization problems, represented by a three-tuple $(f, \mathcal{A}, \mathcal{F})$, where the goal is to maximize the expectation of a stochastic monotone submodular function $f$, subject to a matroid constraint $\mathcal{M}=(\mathcal{A}, \mathcal{F})$. That is, $f: \mathbb{R}_+^n \rightarrow \mathbb{R}_+$ satisfies
$$
\forall~x, y \in \mathbb{R}_+^n: f(x \vee y ) + f(x \wedge y) \leq f(x) + f(y),
$$
where we denote by $x \vee y$ the element-wise maximum and $x \wedge y$ the element-wise minimum of vectors $x$ and $y$. 
The matroid $\mathcal{M}$ captures the feasibility constraint, where  $\mathcal{A}=\{X_1, X_2, ..., X_n \}$ is a ground set of $n$ \textit{independent} random variables, and $\mathcal{F}$ is a collection of independent sets.\footnote{Definition of a matroid $\mathcal{M}=(\mathcal{A}, \mathcal{F})$: all elements of $\mathcal{F}$ are subsets of $\mathcal{A}$ satisfying the following properties: (i) $\emptyset \in \mathcal{F}$; (ii) If $A \in \mathcal{F}$ and $B \subseteq A$, then $B \in \mathcal{F}$; (iii) If $A \in \mathcal{F}$, $B \in \mathcal{F}$ and $ \mid B \mid  >  \mid A \mid $, then there exists $b \in B \setminus A$ with $A \cup \{b\} \in \mathcal{F}$. }

A policy $\pi$ generates a sequence of \textit{selections} of elements in the ground set. 
More precisely, it is a mapping from the set of all possible states to a distribution over elements in the ground set. 
After each selection, the realization of the corresponding element is revealed and the policy may adapt to this new information accordingly. 
The state of this problem $\Theta$ can be described by an $n$-tuple $(\theta_1, \theta_2, ..., \theta_n)$, where $\theta_i$ denotes the realization of $X_i$, if $X_i \in \mathcal{A}$ is selected by the policy, and is equal to $\circ$ otherwise, which means this element has not been selected yet. 
We say a policy is adaptive if the selection decisions are based on the outcomes of the previous actions; otherwise, we say that a policy is nonadaptive. 
Denote by $\Theta^\pi$ the random $n$-tuple corresponding to the last state reached by the policy $\pi$. The value of this policy is defined to be $\mathbb{E}\Big[f(\Theta^\pi)\Big]$. 
We denote by $\mathfrak{F}(\mathcal{A}, \mathcal{F})$ the set of feasible policies, in which the set of elements chosen by $\pi$ always belong to $\mathcal{F}$.

The goal of this optimization problem is to find a feasible policy with respect to $\mathcal{M}$ that obtains the maximum expected value of its final state, i.e.,
\begin{equation}\label{eq:submodular_form}
  \max_{\pi \in \mathfrak{F}(\mathcal{A}, \mathcal{F})}  \mathbb{E} \Big[f(\Theta^\pi)\Big].    \nonumber
\end{equation}


In what follows, we restate the main result of \cite{asadpour2015maximizing} as a theorem, which we will use as the main machinery for our analysis.
\begin{theorem} \label{lemma:borrowed_machinery} (\cite{asadpour2015maximizing}, Theorem 1).
There exists a nonadaptive policy that achieves $1-\frac{1}{e} \approx 0.63$ fraction of the optimal policy in maximizing a stochastic monotone submodular function with respect to a matroid constraint $(f, \mathcal{A}, \mathcal{F})$.
\end{theorem}


\subsubsection{Modeling Pandora's box problem with sequential inspection as a submodular optimization problem.} \label{subsec:submodular_problems}
The Pandora's box problem can be essentially viewed as a selection problem. 
Following Lemma \ref{lemma:committing} and the discussion above, we define two associated problems that capture exactly the tradeoff of inspection modes. 

\begin{definition} \label{def:submodular_optimization}
(The associated stochastic submodular optimization problems). Given an instance of a real-world problem $\mathcal{I}$, which has $N$ boxes with costs and distributions $\left\{c_i^F,c_i^P, \mathcal{D}_i \right\}_{i=1}^{N}$, we define two stochastic submodular optimization problems $\mathcal{J}=\left(f, \mathcal{A}, \mathcal{F}\right)$ and $\mathcal{J}'=\left(f, \mathcal{A}', \mathcal{F} \right)$ associated with the free-info problem:
\begin{itemize}
    \item {\em Ground sets}. We define the ground set $\mathcal{A}$ is
        $$
        \mathcal{A} = \{ K_1, \widetilde{K}_1, K_2, \widetilde{K}_2, ..., K_N, \widetilde{K}_N  \},
        $$
        where $K_i$ and $\widetilde{K}_i$ are correlated and induced from $\mathcal{D}_i$. Thus, $\mathcal{I}$ and $\mathcal{J}$ are defined over the same probability space. However, the ground set $\mathcal{A}'$ is
        $$
        \mathcal{A}' = \{ K_1', \widetilde{K}_1', K_2', \widetilde{K}_2', ..., K_N', \widetilde{K}_N'  \},
        $$
        where $K_i'$ and $\widetilde{K}_i'$ are drawn independently from the same distribution as $K_i$ and $\widetilde{K}_i$.
        
    \item { \em Matroid constraint}. The matroid constraint $\mathcal{M}$ is defined by the partition matroid whose independent sets are all the subsets of $\mathcal{\mathcal{A}}$ (resp., $\mathcal{\mathcal{A}}'$) that contain at most one element of each pair $\{K_i, \widetilde{K}_i \}_{i=1}^{N}$ (resp., $\{K_i', \widetilde{K}_i' \}_{i=1}^{N}$).
    
    \item { \em Objective function}. The submodular objective function $f: \mathbb{R}^{2N}_{+} \rightarrow \mathbb{R}_{+} $ is defined as 
    $$
    f(\Theta) = \max\{ \Theta_i: 1 \leq i \leq 2N , \theta_i \neq \text{ NULL}\}. 
    $$
    We denote the expected profit of policy $\pi$ in $\mathcal{J}$ by $J^{\pi, M}(s_0)$ % $u_{\rm{III}}(\pi)$ 
    and in $\mathcal{J}'$ by $J^{\pi, M'}(s_0)$. 
    % $u_{\rm{III}}'(\pi)$.
\end{itemize}


\end{definition}

\paragraph{Remark.}  Clearly, any feasible policy $\pi$ for problem $\mathcal{J}$ is also feasible for problem $\mathcal{J}'$ (that is, $\pi \in \mathfrak{F}(\mathcal{A}, \mathcal{F}) \Leftrightarrow \pi \in \mathfrak{F}(\mathcal{A}', \mathcal{F})$).
A perhaps simple, yet crucial observation is that for any feasible policy $\pi$, we have $J^{\pi, M}(s_0)=J^{\pi, M'}(s_0)$. 
The equality holds by noting that only one single variable from each pair $\{ K_i, \widetilde{K}_i\}$ or $\{ K_i', \widetilde{K}_i'\}$, is picked by any feasible policy.


\begin{table}[htbp]
  \centering
  % \caption{Add caption}
    \begin{tabular}{cl}
    \toprule
    \toprule
    \multicolumn{2}{c}{Summary of Notations for Theorem \ref{thm:1-1/e}} \\
    \midrule
    $\mathcal{I}$ & A real-world instance \\ 
    $\mathcal{J}$ & The corresponding stochastic submodular problem \\
    $\rho$ & A nonadaptive policy in $\mathcal{J}$ \\
    $\Psi(\rho)$ & A committing policy in $\mathcal{I}$ induced by $\rho$ \\
    $\pi$ & Any policy in $\mathcal{I}$ \\
    $\Phi(\pi)$ & The transformed policy in $\mathcal{J}$ from policy $\pi$ \\
    \bottomrule
    \end{tabular}%
  \label{tab:addlabel}%
\end{table}%

\subsubsection{Transformation of policies.} \label{subsec:submodular_transformation} 

Let $\rho$ be a \textit{nonadaptive} policy in $\mathcal{J}$ and $A(\rho) \subseteq \mathcal{A}$ be the set of random variables that $\rho$ selects. Let $F(\rho)$ denote the (deterministic) set of boxes $\{ i \in [N] \mid K_i \in A(\rho) \}$ and let $P(\rho)$ denote the (deterministic) set of boxes $\{ i \in [N] \mid \widetilde{K_i} \in A(\rho) \} $. Clearly, the expected profit of policy $\rho$ in $\mathcal{J}$ is
\begin{equation}\label{eq:u_III}
  J^{\rho, M}(s_0)  = \mathbb{E} \Big[  \max \big\{  \max_{i \in F(\rho) }\{ K_i \},    \max_{i \in P(\rho)}\{ \widetilde{K}_i  \}  \big\}  \Big].  \nonumber
\end{equation}
Moreover, $\rho$ naturally induces a corresponding committing policy $\Psi(\rho)$ in $\mathcal{I}$ by specifying $F=F(\rho)$ and $P=P(\rho)$. 
We mention in passing that $F \cup P$ might not be equal to $[N]$, but as long as $F \cap P = \emptyset$, Lemma \ref{lemma:committing} still holds. Thus, we have
\begin{equation}
    J^{\Psi(\rho)}(s_0)  =  \mathbb{E} \Big[  \max \big\{  \max_{i \in F(\rho) }\{ K_i \},    \max_{i \in P(\rho)}\{ \widetilde{K}_i  \}  \big\}  \Big].  \nonumber
\end{equation}
Since $\mathcal{I}$ and $\mathcal{J}$ share the same probability space, we have the following lemma:

\begin{lemma} \label{lemma:committing_nonadaptive}
Let $\rho$ be a nonadaptive policy in $\mathcal{J}$, and $\Psi(\rho)$ be the corresponding committing policy in $\mathcal{I}$. We have 
$J^{\Psi(\rho)}(s_0) = J^{\rho, M}(s_0) = J^{\rho, M'}(s_0)$.% $u_{\rm{I}}\left(\Psi(\rho)\right) = u_{\rm{III}}(\rho) = u_{\rm{III}}'(\rho)$.
\end{lemma}


Conversely, let $\pi$ be any policy in $\mathcal{I}$. 
Since problem $\mathcal{I}$ and problem $\mathcal{J}$ share the same probability space, we transform $\pi$ into policy $\Phi(\pi)$ in $\mathcal{J}$ in the following way: 
(i) if policy $\pi$ directly F-opens box $i$ without a P-opening in $\mathcal{I}$, then policy $\Phi(\pi)$ selects $K_i$ in $\mathcal{J}$;
(ii) if policy $\pi$ P-opens box $i$ in $\mathcal{I}$, then policy $\Phi(\pi)$ selects $\widetilde{K}_i$ in $\mathcal{J}$;
(iii) if if policy stops in $\mathcal{I}$, then policy $\Phi(\pi)$ does not select any other box as well. 



\begin{lemma} \label{lemma:adaptivity_gap_bridge}
Let $\pi$ be a policy in $\mathcal{I}$, and $\Phi(\pi)$ be the corresponding transformed policy in $\mathcal{J}$. We have 
$J^{\Phi \left(\pi \right), M'}(s_0) = J^{\Phi \left(\pi \right), M}(s_0) \geq J^{\pi}(s_0)$.
\end{lemma}

\begin{myproof}
By construction, given any policy $\pi$ in $\mathcal{I}$,  the \textit{random} set of random variables selected by the transformed policy $\Phi(\pi)$ in $\mathcal{J}$  is $\{K_i \mid \indFi^{\pi}=1 \} \cup \{ \widetilde{K}_i \mid \indPi^{\pi} = 1 \}$.  
Let $F(\pi) = \{ i \in [N] \mid \indFi^{\pi}=1 \}$ be the random set of boxes that is directly F-opened by policy $\pi$, and similarly, let $P(\pi) = \{ i \in [N] \mid \indPi^{\pi}=1 \}$ be the set of boxes that will be P-opened first by policy $\pi$.
Thus, the expected profit of $\Phi(\pi)$ in $\mathcal{J}$ is % For convenience, denote $\hat{K}_{i}=\left\{\begin{array}{rl}{K_{i}} & {\text { if } \indFi^{\pi}=1} \\ {\widetilde{K}_{i}} & {\text { if }  \indPi^{\pi} = 1}\end{array}\right.$
\begin{equation}
 J^{\Phi \left(\pi \right), M}(s_0) =   \mathbb{E} \Big[  \max \big\{  \max_{i \in F(\pi) }\{ K_i \},    \max_{i \in P(\pi)}\{ \widetilde{K}_i  \}  \big\}  \Big].    \label{eq:lemma_gap_1}
\end{equation}
We emphasize that the expectation is taken over $F(\pi)$ and $P(\pi)$ in addition to $K_i$ and $\widetilde{K}_i $, since the policy can adaptively adjust which inspection mode to apply on boxes based on the observed information.
On the other hand, we note that 
\begin{eqnarray}
J^{\pi}(s_0)  &\leq& \mathbb{E} \Big[ \sum_{i=1}^{N} \indSi^{\pi} K_i(1-\indPi^{\pi} )+\indSitilde^{\pi} \widetilde{K}_i \indPi^{\pi}    \Big]  \nonumber \\ % ~~~\text{by  Cor. \ref{cor:free_info_problem}}\nonumber  \\
   &=& \mathbb{E} \Big[ \sum_{i \in F(\pi) } \indSi^{\pi} K_i + \sum_{i \in P(\pi) } \indSitilde^{\pi} \widetilde{K}_i \Big] \nonumber  \\
   &\leq&  \mathbb{E} \Big[  \max \big\{  \max_{i \in F(\pi) }\{ K_i \},    \max_{i \in P(\pi)}\{ \widetilde{K}_i  \}  \big\}  \Big],   \label{eq:lemma_gap_2}  \\
   &=& J^{\Phi(\pi), M}(s_0)  ,   \label{eq:lemma_gap_3}
\end{eqnarray}
where inequality~\ref{eq:lemma_gap_2} proceeds from the constraint that only one box can be selected. 
Equation~\ref{eq:lemma_gap_3} follows by noting equation~\ref{eq:lemma_gap_1}, and that $\mathcal{I}$ and $\mathcal{J}$ share the same probability space.
% Finally note that  \eqref{eq:lemma_gap_1} and \eqref{eq:lemma_gap_2} are equal, since   
\end{myproof}



Armed with the preceding results,  we are ready to establish our main theorem. 

\subsubsection{Proof of Theorem~\ref{thm:1-1/e}.}  \label{subsec:proof_of_thm:1-1/e}


Let $\pi$ be the optimal policy in $\mathcal{I}$. By Lemma \ref{lemma:adaptivity_gap_bridge}, we have
\begin{equation}
 J^{\Phi(\pi), M'}(s_0)  = J^{\Phi(\pi), M}(s_0)  \geq J^{\pi}(s_0) \triangleq  J^{}(s_0) \ . \label{eq:thm:1-1/e_1}  %  u_{\rm{I}}(\pi)  \triangleq u^*_{\rm{I}}
\end{equation}
By Theorem~\ref{lemma:borrowed_machinery}, there exists a nonadaptive policy $\rho$ in $\mathcal{J}'$ such that
\begin{equation}
  J^{\rho, M}(s_0)  \geq \left( 1- \frac{1}{e} \right)   J^{\Phi(\pi), M'}(s_0) \ .  \label{eq:thm:1-1/e_2}
\end{equation}
By Lemma~\ref{lemma:committing_nonadaptive}, we know that the transformed policy $\Psi(\rho)$ in $\mathcal{I}$ satisfies
\begin{equation}
  J^{\Psi(\rho)}(s_0)  = J^{\rho, M}(s_0) = J^{\rho, M'}(s_0) \ .  \label{eq:thm:1-1/e_3}
\end{equation}
Combining \ref{eq:thm:1-1/e_1}, \ref{eq:thm:1-1/e_2} and \ref{eq:thm:1-1/e_3} together yields
\begin{equation}
  J^{\Psi(\rho)}(s_0) \geq \left( 1- \frac{1}{e} \right) J(s_0)  \ .  \nonumber
\end{equation}

Finally, we remark here that a good committing policy can be found efficiently, by invoking another technical result established in \cite{asadpour2015maximizing}, which we restate as follows. 
\begin{theorem} \label{lemma:borrowed_machinery_2} (\cite{asadpour2015maximizing}, Theorem 2).
For any $\epsilon > 0$ and any instance $(f, \mathcal{A}, \mathcal{F})$, a nonadaptive policy that obtains a $(1 - 1/e - \epsilon)$-fraction of the value of the optimal adaptive policy can be found in polynomial time with respect to $\mid \mathcal{A} \mid$ and $1 / \epsilon$.
\end{theorem}



\subsection{Proof of Theorem~\ref{thm:hardness}}
\label{sec:proof_thm_hardness}

\input{appendix/hardness}