


Next, we study a special case of PSIs whereby boxes are statistically identical and independent, contain binary Bernoulli prizes, and belong to one of two types---``good'' or ``bad.'' We refer to this problem as PSI-B2I (Bernoulli, 2-type, identical and independent).
This setting applies to situations where a decision maker is searching for a satisfactory alternative among options that are initially perceived as equivalent. Partial inspection reveals whether an alternative is promising (``good'') or has low potential (``bad''), while full inspection discloses the exact outcome. 
Several variants of this problem in which the decision maker cannot inspect boxes sequentially have been studied in the literature \citep[see, e.g.][and the references therein]{doval2018whether}.
Our setting is also different from \cite{clarkson2020fast} who assume that there is exactly one prize hidden in the boxes and that opening can be done repeatedly (which does not fit our motivating applications).


In striking contrast to the problem class with binary prizes which is shown to be NP-hard (Section~\ref{sec:np_hardness_mainbody}), the optimal policy to PSI-B2I admits a simple and intuitive structure. 
To formally describe it, we first remark that the equivalence of boxes implies that their opening thresholds are equal; hence, we will refer to them as $\sigma^F$ and $\sigma^P$.
If $\sigma^F \geq \sigma^P$, the optimal policy is fully characterized by Theorems~\ref{thm:myopic_stopping} and~\ref{thm:just_strong}: the optimal policy F-opens closed boxes until a prize is found.



In the difficult case $\sigma^P > \sigma^F$, we denote by $n_C, n_G, n_B$ the number of closed, good and bad boxes, respectively, in the current state. 
Our main result in this section shows that there exists a threshold $N_C$ on the number of closed boxes so that when $n_C > N_C$, an optimal policy exclusively P-opens closed boxes until stopping or reaching a state in which $n_C \leq N_C$, at which point it exclusively F-opens closed boxes. 
We note that the threshold $N_C$ is fixed and independent of the state. 
Moreover, an optimal policy immediately F-opens good-type boxes upon discovery, while postponing bad-type boxes until all closed boxes have been at least partially opened. 
There are exactly $N$ such policies---corresponding to each value of $N_C$---that can be easily enumerated and evaluated for the purpose of optimization.

The structure of the policy above captures the case $\sigma^P \leq \sigma^F$, using the convention $N_c=\infty$.  We also observe that the special case where $\sigma^F < \sigma^P$ and $\sigma^{F/P} \leq 0$ is subsumed by Theorem~\ref{thm:just_weak_closed} (see  Observation~\ref{obs:thresholds_order}), in which case $N_c=0$. Therefore, to ease our analysis, we make  \textbf{without loss of generality} the following simplifying assumption:
\begin{assumption}\label{assumption:b2i}
    The boxes of PSI-B2I satisfy: 
    $0<\sigma^{F/P}<\sigma^F < \sigma^P.$
\end{assumption}


\begin{theorem} \label{thm:iid_optimal}
    For a PSI-B2I instance satisfying Assumption~\ref{assumption:b2i}, there exists an optimal policy $\pi$ that satisfies the following properties: 
    \begin{enumerate}
        %\item $\pi$ stops iff $y=1$ or all boxes are open.
    
        %\item Policy $\pi$ is a committing policy.
        

        \item Policy $\pi$ assigns the highest priority to F-opening good-type boxes.

        \item Policy $\pi$ either discards all bad-type boxes, or  assigns the lowest priority to F-opening them.
        
        \item 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$.

    \end{enumerate}
\end{theorem}

The proof can be found in Appendix~\ref{sec:proof_iid_optimal}. 
{ 
The theorem is presented as an algorithm in Appendix~\ref{sec:algo_psi_b2i}.
}


 
The structure of the optimal policy suggests that the relation between the opening thresholds is the primary factor that determines whether or not P-opening should be considered. 
If $\sigma^P > \sigma^F$ then P-opening should be considered to identify ``promising'' boxes. This option is exerted whenever there are sufficiently many a priori equivalent alternatives (as captured by the threshold rule $n_C > N_C$).
% is beneficial when there are many a priori equivalent dominant alternatives. 
Intuitively, due to the uncertainty about finding good-type boxes, multiple boxes must be P-opened to obtain with high probability a satisfactory outcome. By contrast, when the total number of boxes is small, the decision-maker will most likely end up opening most of them and therefore P-opening is not beneficial. 

{ 
Observe that this policy satisfies the optimal characterization given in Theorems~\ref{thm:myopic_stopping}-\ref{thm:just_weak_closed}; 
indeed, the proof in Appendix~\ref{sec:proof_iid_optimal} directly builds on these properties.
Interestingly, although PSI-B2I is a special case, much of the structure exhibited by the optimal policy for this instance extends naturally to the broader class of PSI problems.
For example, it is useful to consider a class of policies that commit ex ante to fully or partially opening each closed box before execution; this notion of a committing policy proves useful in the general problem and is discussed in detail in Section~\ref{subsec:apx_policies}.
As another illustration, the instance highlights how an increase in the number of boxes makes partial opening more advantageous, a phenomenon that we further validate numerically in Section~\ref{sec:exploring_p_opening_main}. 
}



