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


We conduct numerical experiments to further explore the characteristics of optimal policies and assess the effectiveness of natural candidate policies.
Section~\ref{sec:numerical_instances}  describes the process for generating a diverse set of problem instances. 
Section~\ref{sec:numerical_jay} quantifies the extent to which our theoretical characterization captures optimal decisions. 
Section~\ref{sec:numerical_index} compares the performance of various policies inspired by theoretical analysis. 
Finally, in Section~\ref{sec:exploring_p_opening_main}, we examine factors that increase the tendency of the optimal policies to P-open. 



\subsection{Problem instances}  \label{sec:numerical_instances}

Our design of numerical experiments is based on the observation that the interaction between opening thresholds significantly impacts the behavior of optimal policies. We therefore create instances that consist of boxes with diverse values of opening thresholds.

We begin by generating a collection of ``prototypical'' boxes. 
To create a prototypical box $i$, we sample 5 values for the support of $V_i$ from the uniform distribution $\mathcal{U}(0,10)$; every type $T_i$ can realize up to at most three types (that is, $ \mid \Gamma_i \mid  \leq 3 $); for each type we uniformly sample the conditional distribution $V_i \mid T_i = t$ over the support; we sample the F-opening and P-opening costs from the uniform distributions $\mathcal{U}(0,5)$ and $\mathcal{U}(0,3)$, respectively. We then generate a candidate set of prototypical boxes out of which we select a small representative set (Figure~\ref{fig:scatter_boxes0}).

Each problem instance consists of randomized copies of the prototypical boxes, in varying compositions with $N=2$ to $N=16$ boxes. Due to running time limitations, there are 1000 instances whose size is 2 to 9 (``small instances'' which can be solved to optimality using DP), and there are 300 instances whose size is 10 to 16 (``large instances'' which can only be solved using heuristics).
To avoid trivial cases, we only generate boxes where $c^F_i \geq c^P_i$ (which is why in Figure~\ref{fig:scatter_boxes0} most prototypical boxes have greater P-thresholds). 

 

\subsection{Quantifying the coverage of analytical results} \label{sec:numerical_jay}

The analysis of Section~\ref{sec:characterization} revealed various insights about the nature of the optimal policy. Since the analysis includes sufficient but not always necessary conditions, we are interested in understanding to what extent the sufficient conditions of Theorems 1--3 describe an optimal policy. 

To this end, we conduct two types of experiments. First, we examine optimal solutions to the ``small instances'' and compute the percentage of states where the sufficient conditions of Theorems 1--3 hold (i.e., where our theorems prescribe optimal actions). 
We implement the DP recursion in \eqref{eq:Bellman_Equation} and compute {\em coverage rates}, defined as the percentages of system states where the optimal action can be determined by our sufficient conditions. 


The results are summarized in Table~\ref{tab:util_suff_thms}. The overall coverage rate is presented in the 5th column, and is divided into specific conditions in the 2nd to 4th columns. 
Looking at the 5th column of the table, we see that as the problem increases in size, the sufficient conditions of Theorems 1--3 capture optimal actions in all but a relatively few states. 
The last two columns present the recall of Theorems 2 and 3. These reflect the percentage of states in which the sufficient conditions of the theorems hold out of all states where F-opening (column 6) and P-opening (column 7) are optimal. For example, for instances of size 5 (4th row in the table), Theorem 2 captures 97\% of states where F-opening is optimal, and Theorem 3 captures 77\% of all states where P-opening is optimal.
We observe that identifying P-opening is more challenging than identifying when F-opening is optimal, but overall, the experiment suggests that our characterization explains to a large degree the behavior of the optimal policy. Note that the recall of Theorem 1 is 100\% as the theorem perfectly describes when stopping is optimal. 



We conduct a second experiment where we compare two DP implementations that recursively compute the optimal policy. The first policy ``Na\"ive DP'' is implemented using the DP recursion in Equation~\eqref{eq:Bellman_Equation}, which does not leverage any structure of the optimal policy. The second implementation, on the other hand, utilizes the sufficient conditions of Theorems 1--3 which determine optimal actions and do not require calling the DP recursion when the conditions are satisfied.  Table~\ref{tab:comparison_DP_JAY} compares the two approaches in terms of the total number of states created, the total number of visits to system states, and the runtime. We see that the characterization of the optimal policy not only provides insights about the optimal policy, but also bears computational benefits, allowing to solve problems at significantly shorter times. That  said, the ``curse of dimensionality'' cannot be avoided, as can be observed by the rate at which the size of the state space grows. 





\subsection{Policy benchmark and computational study}
\label{sec:numerical_index}
We evaluate and compare various policies that arise in our analysis: 
\begin{itemize}
    \item $\pi^\textrm{OPT}$ -- the optimal policy, computed by solving the DP naively.
    \item $\pi^{F^*,P^*}$ -- the best committing policy, obtained through complete enumeration. 
    \item  $\pi^{\textrm{index}}$ -- an index policy defined using the opening thresholds associated with every box and action.
    In every state, the policy acts according to the largest index, where the thresholds $\sigma^F_i$, $\sigma^{F \mid t_i}_i$, and $\sigma^P_i$ serve as indices for the F- and P-opening actions, while $y$ is the index for selecting the best opened box.
    This policy is asymptotically optimal (Corollary~\ref{lemma:infinite_iid_boxes}) and
    satisfies the sufficient optimality conditions. 
    \item $\pi^{\textrm{W}}$ -- a one-step lookahead policy \citep{bertsekas2019reinforcement}  based on approximate value functions 
    using Whittle's integral.\endnote{
Another natural policy to consider is the one-step lookahead policy that uses $J^K$ to approximate the  value function. However, given that $J^{W}$ provides a tighter upper bound (Lemma~\ref{thm:upper_bounds}), we only test $\pi^W$ in the experiments.}
    \item $\pi^{STP}$ -- a  policy that determines its next action based on the maximal myopic improvement (using a single ``test,'' hence Single Test Policy) in comparison to stopping. Computing the improvement from each non-open box becomes tractable by ignoring other non-open boxes, and follows the optimal policy for the single box problem (see Figure~\ref{fig:example_1}).
    
\end{itemize}


To evaluate performance, we measure the value function and runtime of each problem instance under different policies, starting from the initial state. As the expected profit can vary significantly among different instances, we normalize the expected profit of each policy relative to the optimal value obtained by policy $\pi^\textrm{OPT}$. 
For large instances where the optimal policy cannot be computed, we use the best-performing policy to normalize the expected profit.
Thus, the performance of each policy is reported as a number between 0 and 1, where larger values indicate better performance. For each policy and a set of instances, we report on performance using the average  across instances and the worst instance tested.



\textit{Average performance. } All heuristics perform quite well in terms of their average performance, often exceeding 90\% of $\textrm{OPT}$. 
However, $\pi^{\textrm{index}}$ and $\pi^{F^*,P^*}$ are superior, with average performances that are close to 100\%.

\textit{Worst-case performance.} We observe that $\pi^{\textrm{W}}$ can perform poorly, at times nearing zero profit. 
This suggests that Whittle's integral approach may not be a suitable approach to deriving tight bounds for our problem, and perhaps to other Pandora's box problems as well.
We also see that $\pi^{\textrm{index}}$ is superior to $\pi^{STP}$ and that its relative performance improves as the number of boxes increases.
We observe that $\pi^{\textrm{index}}$ approaches optimality as $N$ increases, which is aligned with its asymptotic optimality.
Outperforming all others is policy $\pi^{F^*,P^*}$, which achieves the best worst-case performance, with a loss of at most 7\% for instances of size 2. This suggests that index policies based on our opening thresholds are effective for solving the problem. 
We note, however, that this policy is not optimal, and finding the optimal committing policy is computationally challenging \citep[an approximation algorithm is provided in][]{asadpour2015maximizing}. 


\textit{Runtime. } Table~\ref{fig:optimality_boxplot} in Appendix~\ref{apx:tables} summarizes the runtimes. 
As expected, the time for solving instances to optimality grows exponentially fast, making it challenging to solve instances with more than 9 boxes. 
We also see that applying policy $\pi^{\textrm{W}}$ becomes more challenging as the number of boxes increases, due to the calculation of Whittle's integral.
Similarly, the exhaustive enumeration carried out by policy $\pi^{F^*,P^*}$ could result in long runtimes.
We note that the runtime also depends on the size of the support of the distribution (which we assumed to be 5) and the number of box types (which we assumed to be at most 3).
Note that these runtimes include the entire calculation of the value function and that simply applying these policies is very fast.



\textit{Optimality. }
Table~\ref{tab:comparison_of_J} shows the percentage of instances for which different policies attain the optimal expected objective value. 
In contrast to the near-optimal performance displayed in Table~\ref{tab:performance_with_DP}, policy $\pi^{\textrm{W}}$ is almost never optimal. Additionally, even policies $\pi^{F,P}$ and $\pi^{\textrm{index}}$, which perform better, in many cases do not achieve the optimal objective value. We notice that overall, the performance of the latter two index policies improves with the number of boxes, which aligns with the asymptotic optimality result (Corollary~\ref{lemma:infinite_iid_boxes}).



\subsection{When is P-opening worthwhile?}
\label{sec:exploring_p_opening_main}


We next conduct experiments that shed light on the structure of optimal policies and further characterize when P-opening is worthwhile.

To this end, we define the notion of \textit{P-ratio} as the average percentage of P-openings conducted by the optimal policy of all opening actions. A higher P-ratio implies that the optimal policy applies P-opening more frequently. We compute the P-ratio for a set of problem instances and plot it against various problem characteristics. For brevity, we describe the main results below and postpone the complete details of the experiment and the figures to Appendix~\ref{sec:numerical-apx}. 

One of our main findings is that greater homogeneity of boxes in terms of their opening thresholds (i.e., boxes $i$ and $j$ are ``homogeneous'' when the tuples $(\sigma^F_i,\sigma^P_i)$ and $(\sigma^F_j,\sigma^P_j)$ are close) is correlated with  more frequent partial opening. This aligns with intuition, since when boxes are very different, their relative value can be determined without partial inspection; hence, F-opening can simply be conducted as a necessity prior to selection. 

Additionally, in line with our theoretical results, we observe an increased tendency to partially open when there is a higher proportion of boxes whose P-thresholds exceed their corresponding F-thresholds.
This finding underscores the role of opening thresholds in capturing the value of corresponding inspection modes.

Finally, in the case of identical boxes (homogeneity is maximal), the tendency to partially open increases in the number of boxes. This suggests that when the pool of alternatives is larger, partial opening becomes more significant---assuming partial opening is worthwhile to begin with. 










%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Conclusions and Future Directions}
\label{sec:conclusion}

The work studies a generalized Pandora's box problem that captures a tradeoff related to acquiring accurate and costly versus inaccurate but cheaper information about the value of competing alternatives. 
We proved that the problem is NP-hard, but nevertheless, using a synthesis of techniques, we identified structural properties of the optimal policy and provided insights into the key drivers of optimal information acquisition decisions. 
We showed that intuitive threshold-based policies that extend the Pandora's box solution describe optimal decisions and form the basis of approximate solutions. Extensive numerical experiments show that this characterization almost entirely explains the optimal policy, and that the approximate policies perform extremely well. 




As our work focused on the simplest yet sufficiently rich context where the aforementioned tradeoff occurs, it would be interesting to consider more general settings. For example, a richer information model that allows multiple types of repeated inspections, inspection costs that decrease after inspections take place, and the option to select partially opened boxes, all could be interesting directions for future work. 