\section{Simple Approximately Optimal Policies}
\label{sec:apx}
We establish that computing optimal policies for PSI is NP-hard (Section~\ref{sec:np_hardness_mainbody}). 
We therefore turn our attention to the development and analysis of simple approximate solutions that utilize relaxations that approximate the value function. 
In Section~\ref{subsec:upper_bounds}, we propose two approximation methods: {\em Whittle's integral} and the {\em free-info relaxation}, which adapt tools from related literature. Interestingly, we show that Whittle's integral provides a tighter upper bound, 
and establish the asymptotic optimality of the index policy based on the opening thresholds. 
In general, we exploit these problem relaxations  in Section~\ref{subsec:apx_policies} to devise approximation algorithms, in particular achieving a $(1-1/e)$-approximation ratio, through a reduction to the maximization of stochastic submodular functions~\citep{asadpour2015maximizing,singla2018price,beyhaghi2019pandora}.


\subsection{Hardness of the problem}  \label{sec:np_hardness_mainbody}

\begin{theorem} \label{thm:hardness}
Computing optimal policies for PSI is NP-hard.
\end{theorem}

The proof strategy involves a reduction from a family of subset sum problems. Specifically, we construct a hard instance in which every box $i$ has two types $|\Gamma_i| = 2$:  ``good" and ``bad." 
The good type is sufficiently valuable that an optimal policy F-opens the box upon discovering it, and bad type boxes are discarded.
Hence, determining the optimal policy is essentially equivalent to deciding how to partition the $N$ boxes, i.e., deciding the opening mode for each box. 
We carefully design this PSI instance so that the partition exactly corresponds to the solution of the subset sum problem. The proof is intricate and appears in Appendix~\ref{sec:proof_thm_hardness}. 
In particular, formalizing the preceding argument requires controlling the encoding error due to the bit precision of the input.

It is interesting to note that the hard instances we constructed for the proof of Theorem~\ref{thm:hardness} are very close to the one subsumed by Corollary~\ref{cor:support_2}, for which we were able to provide a polynomial-time algorithm. Specifically, our family of hard instances satisfies that,  every box $i \in [N]$ has $\sigma_i^P > \sigma_i^F$ and  $ |\Gamma_i| = 2 $. The only difference, however, is that $\sigma_i^{F/P} > 0$, contrary to Corollary~\ref{cor:support_2}.  
This suggests that Corollary~\ref{cor:support_2} is ``tight'' in some sense.


Finally, our reduction from subset partition has some similarities with the NP-hardness proof of \cite{fu2022pandora} in a related computational setting; see Remark~\ref{remark:connections_to_fu} in Appendix~\ref{sec:proof_thm_hardness} where we discuss similarities and important differences in both reduction proofs.




\subsection{Relaxations and upper bounds} \label{subsec:upper_bounds}
A common method to solve high-dimensional DPs consists in approximating the value function \citep[see, e.g.,  Chapter 9 in][]{powell2007approximate}.
For example, effective policies are often obtained by solving the approximate Bellman's equation, where the true (unknown) value function is replaced by its approximate counterpart.
In what follows, we construct two natural upper bounds on $J({\cal C},{\cal P},y)$ and compare them analytically.


\textit{Whittle's integral.}
This is a known upper bound on the value function of MAB superprocesses \citep[see, e.g.,][]{brown2013optimal}. Consider a problem with a single non-fully-open box $i$ where the current maximum prize is $y$. 
Let $\omega_i(y)$ be the probability that the current maximum prize $y$ is eventually selected by an optimal policy. 
In other words, we can think of $\omega_i(y)$ as the probability that the effort of opening box $i$ is in vain, provided that only box $i$ is left.  
Given the characterization of the optimal policy for the single-box case in Theorem~\ref{thm:myopic_stopping}, it is not hard to see that, if box $i \in \mathcal{C}$,
% \begin{small}
$$
 \omega_i\left( y \right)= \BFI\left\{ y > \sigma_i^{F/P}  \right\} \operatorname{Pr} \left[ \min \left\{ V_i, \sigma_i^{F \mid T_i}, \sigma_i^P \right\} \leq y \right] + \BFI\left\{ y \leq \sigma_i^{F/P}  \right\} \operatorname{Pr} \left[  \min \left\{ V_i,  \sigma_i^F \right\} \leq y \right] \ .
$$
% \end{small} 
Otherwise, if box $i \in \mathcal{P}$,
% \begin{small}
$$
\omega_i\left( y \right)=  \operatorname{Pr} \left[ \min\{V_i, \sigma_i^{F \mid t_i} \} \leq y \mid T_i=t_i \right] \ .
$$ 
% \end{small} 
Consequently, Whittle's integral corresponds to  the following quantity:
% \begin{small}
\begin{equation} \label{eq:whittlesintegral}
    J^W( \mathcal{C}, \mathcal{P}, y ) = \sigma_M (\mathcal{C}, \mathcal{P}) - \int_{y}^{\sigma_M(\mathcal{C}, \mathcal{P})} \prod_{i\in {\cal C}\cup {\cal P}} \omega_i( u) du \ .
\end{equation}
We will establish in Lemma~\ref{thm:upper_bounds} that this function provides an upper bound on the $J( \mathcal{C}, \mathcal{P}, y)$. Conversely, when $y = \sigma_M(\mathcal{C}, \mathcal{P})$, we straightforwardly obtain  $J( \mathcal{C}, \mathcal{P}, y) \geq y \geq \sigma_M(\mathcal{C}, \mathcal{P}) \geq  J^W( \mathcal{C}, \mathcal{P}, y )$, implying that the upper bound~\eqref{eq:whittlesintegral} can be tight in certain states.



\paragraph{Free-info relaxation.} We now consider an alternative upper-bounding method that exploits the interpretation of indices as fair strike prices of two-stage call options. To this end, we introduce indicator random variables that describe the actions chosen by any given policy $\pi \in \Pi$ from state $({\cal C},{\cal P},y)$.\endnote{Recall that, in the state description, $y$ is the reward of a best F-opened box. Without loss of optimality, we restrict attention to policies that discard other $F$-opened boxes.} Let $\mathbb{S}_i^{\pi}, \widetilde{\mathbb{S}}_i^{\pi}$ be the binary random variables that indicate whether box $i$ is eventually selected without a partial opening and after a partial opening, respectively. (Note that we necessarily have $\mathbb{S}_i^{\pi} + \widetilde{\mathbb{S}}_i^{\pi} \leq 1$). Similarly, let $\mathbb{F}_i^{\pi},\widetilde{\mathbb{F}}_i^{\pi}$ be the binary random variables that indicate whether box $i$ is F-opened without any prior P-opening or after a P-opening, respectively. Finally, let $\mathbb{P}_i^{\pi}$ be the binary random variable that indicates whether box $i$ is P-opened.  While these decision variables depend on the policy $\pi$, for ease of notation, we sometimes suppress the superscript $\pi$. 
With this notation at hand, the expected value of policy $\pi$ in state $({\cal C},{\cal P},y)$ can be written as 
\begin{equation}
    J^{\pi} ({\cal C},{\cal P},y) =  
    \E{ \left. {\mathbb{S}}_0^{\pi} \cdot y + \sum_{i\in {\cal C}} \left(  \mathbb{S}_i^{\pi} V_i - \mathbb{F}_i^{\pi}  c_i^F - \mathbb{P}_i^{\pi} c_i^P \right) + \sum_{i\in {\cal C} \cup {\cal P} } \left(  \widetilde{\mathbb{S}}_i^{\pi} V_i -  \widetilde{\mathbb{F}}_i^{\pi}  c_i^F \right) \right| ({\cal C},{\cal P},y) }  \ ,
\end{equation}
where, by a slight abuse of notation, the conditional expectation indicates that policy $\pi$ is executed starting from state $({\cal C},{\cal P},y)$, and thus, we only accrue the  costs of future opening decisions and the rewards of future selections decisions. 
Hence, the Pandora's box problem with sequential inspections can be formulated as the following mathematical program:
% \begin{small}
\begin{equation}  \label{eq:obj}
   J ({\cal C},{\cal P},y) = \max_{\pi \in \Pi} ~ J^{\pi} ({\cal C},{\cal P},y)\ . 
\end{equation}
% \end{small} 


The free-info relaxation considers an alternative setting, in which there is no cost of P-opening and F-opening, but instead, the rewards of the boxes are capped according to the threshold values. The notion of a feasible policy does not change in this new formulation, only the cost accounting is modified. Specifically, for every box $i \in \mathcal{C}$, we define the capped value of F-opening to be $K_i = \min\{V_i, \sigma^{F}_i\}$ and the capped value of P-opening to be $\widetilde{K}_i = \min \{ V_i, \sigma^{F \mid T_i}_i, \sigma^{P}_i\} $. Similarly, for every box $i\in {\cal P}$, we define the capped value of type $t_i$ as $\widetilde{K}_i^{t_i} = \min\{ \sigma_i^{F \mid t_i} , V_i \}$.  Consequently, in the free-info formulation, the expected reward of policy $\pi$ in state $({\cal C},{\cal P},y)$ is
\begin{eqnarray}
  J^{\pi,K} (\mathcal{C}, \mathcal{P}, y)  
    &=&   \mathbb{E}\left [ \left. {\mathbb{S}}_0^{\pi} \cdot y + \sum_{i\in {\cal C}}  \left(\mathbb{S}_i^{\pi} K_i + \widetilde{\mathbb{S}}_i^{\pi} \widetilde{K}_i \right)+ \sum_{i\in {\cal P} }  \widetilde{\mathbb{S}}_i^{\pi}  \widetilde{K}^{t_i}_i  \right| ({\cal C},{\cal P},y) \right] \label{eq:free} \ . 
\end{eqnarray}
Recall that we interpret the caps as fair strike prices of call options on the box values, whose expected payoff offsets the opening costs. The formulation~\eqref{eq:free} can be viewed as an alternative cost accounting where Pandora opens boxes free of charge (there are no negative terms), and in exchange, there is a short position on a call option that exactly compensates the opening costs. However, Pandora has the advantage of being subjected to the short contract only if the box is ultimately selected; otherwise, the short contract is void. Under this optimistic assumption, Pandora essentially collects one of the capped rewards, $K_i$, $\widetilde{K}_i$, or $\widetilde{K}^{t_i}_i$, depending on the chosen opening mode. 

Going one step further, the free-info relaxation in state $(\mathcal{C}, \mathcal{P}, y)$ corresponds to the following quantity:
\begin{eqnarray}\label{freeinfo:ub}
J^K (\mathcal{C}, \mathcal{P}, y) = \mathbb{E}\left[  \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\} \right] \ .
\end{eqnarray}
Similarly to Whittle's integral, we eliminate the dependence on policy $\pi$ by choosing the box with the highest capped reward. Therefore, $J^K (\mathcal{C}, \mathcal{P}, y) $ is an upper bound on~\eqref{eq:free}, which might not be attainable through a specific policy $\pi$. 

We are now ready to state our main result with respect to Whittle's integral and the free-info relaxation, showing that both methods provide valid upper bounds on the value function.
\begin{lemma}\label{thm:upper_bounds}
For every state $(\mathcal{C}, \mathcal{P}, y)$, we have
\begin{equation}
   J(\mathcal{C}, \mathcal{P}, y)  \leq J^W (\mathcal{C}, \mathcal{P}, y)  \leq  J^K (\mathcal{C}, \mathcal{P}, y) \ .
\end{equation}
\end{lemma}
The proof appears in Appendix~\ref{appendix:thm:upper_bounds}. 
These upper bounds have been independently derived in the literature for related optimization settings. To our knowledge, this result is the first to formally connect these methods and show that Whittle's integral provides a tighter upper bound. 
The proof relies on results by~\cite{brown2013optimal} who exhumed an unnoticed technical claim in~\cite{whittle1980multi} to derive Whittle's integral (for the cost-discounted case), and \cite{beyhaghi2019pandora} who proposed the free-info relaxation; a technical difference in our setting is that information can be acquired sequentially over multiple stages. 



We note in passing that Lemma~\ref{thm:upper_bounds} can be used to establish the asymptotic optimality of the index policy that prioritizes the highest threshold inspection. For brevity, we relegate this result to Appendix~\ref{appendix:ex_infinite_iid_boxes}.




\subsection{Near-optimal algorithms} \label{subsec:apx_policies}


% \paragraph{Approximation algorithm.}
 In this section, we leverage the upper bounds of Section~\ref{subsec:upper_bounds} to construct simple near-optimal policies. Specifically, we develop an algorithm with a worst-case approximation ratio of $(1-1/e)$ using a reduction to the stochastic submodular optimization problem. 
 
 Our approach is an application of the framework by \cite{singla2018price} and \cite{beyhaghi2019pandora}. In this context, the main idea is to focus on policies for which the free-info upper bound $J^{\pi,K}$ of equation~\eqref{eq:free} is exactly equal to the value function $J^{\pi}$ of equation~\eqref{eq:obj}. It turns out there is a simple recipe for constructing such policies: (i) commit before opening any box on the selection mode of each box (i.e., whether we start by F-opening or P-opening it), and (ii) strictly follow the order of decreasing opening thresholds. That is, we partition the set of boxes into two subsets, $[N]= F\cup P$, such that boxes $i\in F$ are initially $F$-opened, whereas boxes $i\in P$ are $P$-opened, if inspected. Next, in each state, we select the action with the highest associated threshold. The resulting class of policies $\pi^{F,P}$ is termed {\em committing} policies. The reader is referred to the Algorithm~\ref{algo:committing} for a complete description. 


\begin{algorithm}[H]
\footnotesize
  \caption{Committing policy $\pi^{F,P}$.} \label{algo:committing}
  \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 ([N], \emptyset, 0)$;
\While { $y < \max \left\{  
  \underset{j \in \mathcal{C} \cap F }{\max}  \left\{  \sigma_j^F \right\}, 
  \underset{j \in \mathcal{C} \cap P }{\max}  \left\{  \sigma_j^P \right\}, 
  \underset{ j \in \mathcal{P}}{\max }  \left\{ \sigma_j^{F \mid t_j}  \right\}  
  \right\}  $  }
  % \State Let $\sigma_i=\sigma_M (\mathcal{C},\mathcal{P}) $;
  \State Let $ \sigma_i = \max \left\{  
  \underset{j \in \mathcal{C} \cap F }{\max}  \left\{  \sigma_j^F \right\}, 
  \underset{j \in \mathcal{C} \cap P }{\max}  \left\{  \sigma_j^P \right\}, 
  \underset{ j \in \mathcal{P}}{\max }  \left\{ \sigma_j^{F \mid t_j}  \right\}  
  \right\}$; 
\If{$i \in F$}  
    \State F-open box $i$; $~ y \gets \max \{ y, v_i\}$; $~\mathcal{C} \gets \mathcal{C} \setminus \{ i \}$;
    % \State  $ \mathcal{C} \gets \mathcal{C} \setminus \{ i \}$ if $i \in \mathcal{C}$, $ \mathcal{P} \gets \mathcal{P} \setminus \{ i \}$ if $i \in \mathcal{P}$;
\ElsIf{ $i \in P$}
    \If {$i \in \mathcal{C}$}
        \State P-open box $i$; $\mathcal{C} \gets \mathcal{C} \setminus \{ i \};  ~ \mathcal{P} \gets \mathcal{P} \cup \{ (i, t_i)\}$; % ~ \sigma_i \gets \sigma_i^{F \mid t_i}$;
    \ElsIf{ $ i \in \mathcal{P}$}
        \State F-open box $i$; $\mathcal{P} \gets \mathcal{P} \setminus \{(i, t_i)\}; ~ y \gets \max \{ y, v_i\}$;
    \EndIf
    % \State $P \gets P \setminus \{ i \}$;
\EndIf

\EndWhile
\State Select $y$ and stop;
  \end{algorithmic}
\end{algorithm}


The next lemma shows that the expected profit of any committing policy indeed coincides with its free-info upper bound, which can be expressed in a simple form.

\begin{lemma}  \label{lemma:committing}
Given a partition $(F,P)$ of the set of boxes $[N]$,
the committing policy $\pi^{F,P}$ generates an expected profit of
\begin{equation} \label{eq:lemma:committing}
    J^{\pi^{F,P}}(s_0) = J^{\pi^{F,P},K}(s_0)
=
\mathbb{E}\left[ \max \left\{ \underset{i \in F}{\max} \{  K_i\}   , \underset{i \in P}{\max}  \{ \widetilde{K}_i \}  \right\}\right].
\end{equation}
\end{lemma}
 Intuitively, committing policies are not exposed to any cost accounting error, in comparing the opening costs to the corresponding short positions on call options. Recall that this free-info cost accounting is optimistic because Pandora is subjected to the short contract only if the box is ultimately selected. In the proof of Lemma~\ref{lemma:committing}, we identify necessary and sufficient conditions such that Pandora always selects any F-opened box (or F-opens any P-opened box) whenever the call option (or two-stage call option) is in the money. This way, Pandora meets the contractual payment of the option, which is equal to the opening costs in expectation. In particular, we show these necessary and sufficient conditions are met by committing policies.
 
Now, this introduction of such committing policies raises the following question: how should we design the partition $(F,P)$? Can we construct committing policies that achieve strong (constant-factor) approximation ratios? Based on the expected profit characterization of  Lemma~\ref{lemma:committing}, we can compare committing policy $\pi^{F,P}$'s payoff $\mathbb{E}[ \max \{ \underset{i \in F}{\max} \{  K_i\}   , \underset{i \in P}{\max}  \{ \widetilde{K}_i \}  \}]$ to the free-info upper-bound $J^K (s_0) = \mathbb{E}[ \underset{i \in [N]}{\max}   \max\{K_i, \widetilde{K}_{i}  \} ]$ (see Equation~\eqref{freeinfo:ub}).
The former ex-ante chooses either $K_i$ or  $\widetilde{K}_{i}$, before observing their realizations, depending on whether $i\in F$ or $i\in P$. By contrast, the latter chooses the maximum reward $\max \left\{K_i, \widetilde{K}_{i}  \right\} $ out of the two opening modes after seeing their realizations. This informal comparison leads to the design of simple approximation algorithms.

First, note that the following upper bound on the free-info setting always holds:
\begin{eqnarray*}
    J^K \left(s_0\right) &=& \mathbb{E}\left[   \max_{i\in [N]} ~ \max\left\{K_i, \widetilde{K}_{i}  \right\}  \right] \\
    &\leq& \mathbb{E}\left[  \max_{i\in [N]} \left({\mathbb I}[i\in F] \cdot K_i + {\mathbb I}[i\in P] \cdot\widetilde{K}_i\right) + \max_{i\in [N]} \left({\mathbb I}[i\in P] \cdot K_i + {\mathbb I}[i\in F] \cdot \widetilde{K}_i\right) \right] \\
    &= & J^{\pi^{F,P}} \left(s_0\right) + J^{\pi^{P,F}} \left(s_0\right) \ ,
\end{eqnarray*}
where the inequality holds since $\max\{a,b\} \leq \max\{c,d\} +\max\{e,f\} $ for every scalars $a\leq \max\{c,e\}$ and $b\leq \max\{d,f\}$, and the last equality proceeds from Lemma~\ref{lemma:committing}. Importantly, the above inequality implies that, for any partition of $(F,P)$ of $[N]$, either the committing policy $\pi^{F,P}$ or the one $\pi^{P,F}$ that flips the opening modes achieves a factor-$\frac{1}{2}$ approximation of the optimum.

More broadly, the performance of a well-designed committing policy is related to the adaptivity gap in stochastic submodular maximization; the question can be reformulated as optimizing a certain submodular function over random entries and the goal is to bound the gap between non-adaptive policies, that select those entries before their realizations are revealed, and adaptive ones. By leveraging fundamental results in this area, we obtain the following theorem.
\begin{theorem}\label{thm:1-1/e}
There exists a committing policy that achieves at least  $1 - 1/e\approx 0.63$ of the optimum %$u^*_{\rm{I}}$
and can be approached via a polynomial-time approximation scheme.
\end{theorem}
In Appendix~\ref{appendix:thm:1-1/e}, we devise a reduction from Pandora's box problem to the problem of maximizing a stochastic submodular function under additional constraints.
In this context, \cite{asadpour2015maximizing} showed, among other results, that the adaptivity gap (i.e., the performance gap between non-adaptive and adaptive policies) is lower bounded by $1-1/e$, and that an approximate non-adaptive policy can be efficiently constructed using a continuous-greedy algorithm.

