


In this section, we show that computing optimal policies for \textit{Pandora box problem with sequential inspection} (PSI) is NP-hard. 
We devise the reduction from a family of NP-hard subset sum problems. 



\paragraph{\bf The hard instances.} We devise a reduction from the subset sum problem (SSP). We are given positive integers $a_1,\ldots,a_{n}$ and the goal is to find $W \subseteq [n]$ such that $\sum_{i\in W} a_i = T$. Without loss of generality, we assume that $T \leq \frac{1}{2} \sum_{i=1}^{n} a_i $ as otherwise, we consider the complementary target $\sum_{i=1}^{n} a_i - T$, corresponding to selecting the complement in $[n]$. 
For brevity, we use the notation $L \defeq \sum_{i=1}^{n} a_i $ throughout.  
Moreover, we focus on a family of SSP which we call the $\varepsilon$-SSP, where we have $ \frac{a_i}{\sum_{i=1}^{n} a_i} \leq \varepsilon $ for every $i \in [n]$ for some $\varepsilon \in (0,1)$.  
This family is still NP-hard. 
To see this, suppose there exists a polynomial-time algorithm that solves the $\varepsilon_0$-SSP for some fixed $\varepsilon_0$. 
Now given a general SSP instance $\{ \braces{a_i}_{i=1}^{n}, T \}$, we can transform it to a $\varepsilon_0$-SSP instance by adding ``fake items" $a_0 > L$. 
Since $a_0 > L$, we know for sure we will not include them in a feasible solution. 
In addition, we can ensure for every $i \in [n]$, we have $ \frac{a_i}{ N \cdot a_0 + \sum_{i=1}^{n} a_i} < \frac{a_0}{ N \cdot a_0 + \sum_{i=1}^{n} a_i } < \varepsilon_0$ for large enough $N = O(\frac{1}{\varepsilon_0})$ (independent of $n$). 
The following lemma ensues.


\begin{lemma}
    The $\varepsilon$-subset sum problem is NP-hard for any fixed $\varepsilon \in (0,1)$.
\end{lemma}



Our reduction makes use of the following class of PSI instances. 


\begin{definition}[The 2T2L-PSI Instance]
    \label{def:2T2L-PSI_instance}
    Given positive integers $\braces{a_i}_{i=1}^{n}$, an instance of PSI with $n$ boxes is a two-type two-support low-cost-low-return (2T2L) instance  with parameter $(\nu, \alpha)$ where $\nu \in (0,1), \alpha > 0$ if the following conditions hold: 
    \begin{enumerate}
        \item all rewards are binary random variables $V_i \in \{ 0, 1 \}$. Specifically, for box $i$, we set its success probability as 
        $$
    p_i \defeq \pr{V_i = 1} = 1-  \exp\left(- \alpha a_i \right) \ , 
        $$
        for some constant $\alpha>0$. We define $p_i'$ as 
        $$
    p_i ' \defeq  1-  \exp\left(- \frac{1}{2} \alpha a_i \right) \ ; 
        $$
        \item each box $i$ has 2 types: good and bad, $\Gamma_i = \{ G, B\}$, and moreover $\pr{T_i=G}=(1-\nu) p_i $, $\pr{T_i=B}= 1 - (1-\nu) p_i  $, $\pr{V_i=1 \mid T_i=G} = \frac{p_i'}{p_i (1-\nu)} + p_i - p_i' $, $ \pr{V_i=1 \mid T_i=B} = p_i - p_i' $; 
        \item box $i$ has F-opening cost $c_i^F = \frac{3}{5} p_i$ and P-opening cost  $c_i^P = (1-\nu)  p_i \paren{ \frac{1}{3} ( \frac{p_i'}{ p_i (1-\nu) } + p_i - p_i') - \frac{3}{5} p_i } $. 
    \end{enumerate}
\end{definition}

\paragraph{\bf The reduction.}
Given an instance of the $\varepsilon$-Subset Sum Problem ($\varepsilon$-SSP) $\{\{a_i\}_{i=1}^n, T\}$, we construct an associated 2T2L-PSI instance by setting the parameters $\alpha = \frac{\ln(\frac{3}{2})}{L-T}$ and $\nu = \frac{1}{2}$.

We will show that there exists a universal constant $c \in (0,1)$ such that, whenever $\varepsilon < c$, there exists an optimal policy of the associated PSI instance that admits the form of a committing policy (see Section~\ref{subsec:apx_policies} for a formal definition and discussion). 
Specifically, in this associated PSI instance, the good type and the bad type are highly distinguishable. Learning the type of a box directly informs the decision to either F-open it or discard it. If a box is discarded, it has no further impact on any future decisions.
Additionally, as the rewards are binary, it is optimal to stop and select a box immediately upon finding one with a reward of 1. Consequently, there exists an optimal policy for this instance that is a committing policy.
If a PSI instance admits the above-mentioned properties, we call it a \textit{well-separated} instance. 
Suppose that there is an oracle which returns an optimal policy for such a well-separated instance. 
Then one can read off a partition of boxes, of which the policy is committed to the opening mode. 


Moreover, the parameter $\alpha = \frac{\ln(\frac{3}{2})}{L-T}$ of the associated 2T2L-PSI instance is carefully set such that the optimal partition $(F^*, P^*)$ is exactly achieved at the condition $\sum_{i \in P^*} a_i = T$, if such a subset $P^*$ exists. 




One caveat, however, is that in the associated PSI instance, the inputs $p_i$ and $p_i'$ are irrational, potentially requiring exponential bit complexity.
We note that for the purpose of a polynomial-sized reduction,\footnote{The reduction must run in polynomial time in $n \log(\max_{i \in [n]} a_i)$, which is the input size of the $\varepsilon$-SSP instance.} it might be infeasible to feed the \emph{true} associated low-cost-low-return PSI instance to the Pandora oracle. Instead, we approximate the inputs and feed the Pandora oracle an \emph{approximated version}, using $\hat{p}_i$ and $\hat{p}_i'$ as substitutes for $p_i$ and $p_i'$, respectively.

We use 
$$
\delta \defeq \max_{i \in [n]} ~\max \braces{ \frac{\abs{ p_i - \hat{p}_i }}{p_i} ,  \frac{\abs{ p_i' - \hat{p}_i' }}{p_i'} }  
$$ 
to measure the encoding precision. 
In the following lemma, we make it precise the conditions needed for the \textit{true} associated 2T2L-PSI instance to be well-separated. 


Moreover, we characterize the degree of precision needed in the approximated instance to ensure the same optimal policy structure, in terms of a requirement on $\delta$.



\begin{lemma}  \label{lemma:hard_psi_is_committing}
    Consider a 2T2L-PSI instance, with parameter $(\nu, \alpha)$ set to $\alpha=\frac{\ln(\frac{3}{2})}{ L - T}$ where $ 0 < T \leq \frac{1}{2} L$.
    There exists a universal constant $c \in (0,1)$ such that if $\frac{a_i}{L} \leq c $ for every $i$, then an optimal policy F-opens a good box immediately upon observation and discards a bad box (never opens it afterwards) upon discovery. 
    Consequently, there exists an optimal policy which is a committing policy. 
    
    Moreover, $\delta = \Theta(\frac{1}{L})$ ensures that the approximated PSI instance admits an optimal committing policy as well. 

    In addition, an optimal policy must be a committing policy in both cases. 
\end{lemma}


\begin{myproof}

\textbf{First half: the true instance. }

We will show that by construction, there exists a universal constant $c \in (0,1)$ such that if $\frac{a_i}{L} \leq c $ for every $i \in [n]$, then
(1) $\sigma_{i}^{F} = \frac{2}{5} $, 
(2) $\sigma_{i}^{F|G} > \frac{2}{3} $, 
(3) $\sigma_{i}^{F|B} < 0$,
(4) $\sigma_{i}^{P} = \frac{2}{3}$,
(5) $\sigma_{i}^{F/P} > 0$. 
Therefore, by virtue of Theorem~\ref{thm:just_strong}, an optimal policy shall immediately F-open a good box upon finding it. 
By Theorem~\ref{thm:myopic_stopping}, an optimal policy shall discard any bad boxes.  Not only will one never open such a bad box, but also it does not affect any of the subsequent decisions.
Consequently, there exists an optimal policy that is a committing policy.  
It is worth noting that our constructed instance does \textit{not} satisfy the conditions of Corollary~\ref{cor:support_2}, where we have identified the optimal committing policy.

In what follows, we compute each of the above-mentioned thresholds. 
Observe that in order to ensure that $p_i < \theta$ for some $\theta \in (0,1)$, it suffices to require 
\begin{equation} \label{eq:p_i_to_a_L_ratio}
    \frac{a_i}{L} < \frac{ \ln(\frac{3}{2})}{2  \ln(\frac{1}{1-\theta})} \ .  
\end{equation}

\begin{enumerate}
    \item \textbf{The F-threshold $\sigma_{i}^{F} = \frac{2}{5} $.} 
        We recall that $c_i^F = \frac{3}{5} p_i$, $\pr{V_i=1}=p_i$ and
        $$
            \E{ \paren{V_i - \sigma_i^F}^+ } = \pr{V_i=1} \paren{1 - \sigma_i^F}  \ . 
        $$
        Hence, $\sigma_i^F = \frac{2}{5} $ exactly. 
    \item \textbf{The conditional F-threshold $\sigma_{i}^{F|G} > \frac{2}{3} $ .}         
        To see this, we note that by definition 
        $$
        c_i^F = \E{ \paren{V_i - \sigma_i^{F|G} }^+ \mid T_i = G } = \pr{V_i=1 \mid T_i=G} \paren{1 - \sigma_i^{F|G} } \ . 
        $$ 
        Plugging $\pr{V_i=1 \mid T_i=G} = \frac{p_i'}{p_i (1-\nu)} + p_i - p_i'$ into the above equation, we have that 
        \begin{equation} \label{eq:sigma_F_G_true_hard_instance}
            \sigma_i^{F|G} = 1 - \frac{3}{5} \frac{p_i^2}{ \frac{1}{1-\nu} p_i' + p_i (p_i - p_i') } \ . 
        \end{equation}
        In order for $\sigma_i^{F|G} > \frac{2}{3}$, it suffices to set $\frac{p_i^2}{ \frac{1}{1-\nu} p_i' + p_i (p_i - p_i') } < \frac{5}{9}$. 
        By Jensen's inequality, we know 
        $
        \exp \paren{- \frac{1}{2} \alpha a_i  } < \frac{1}{2} \paren{ \exp \paren{- \alpha a_i } + 1  } 
        $
        which implies that 
        \begin{equation} \label{eq:consequence_of_jensen_p_p_prime}
            p_i >  p_i' > \frac{1}{2} p_i \ .     
        \end{equation}
        Hence, $\frac{p_i^2}{ \frac{1}{1-\nu} p_i' + p_i (p_i - p_i') } 
        < \frac{p_i^2}{ \frac{1}{1-\nu} \frac{1}{2} p_i + p_i (p_i - p_i') } 
        < 2 p_i $. It suffices to impose $2p_i < \frac{5}{9}$, for which to happen we can require 
        \begin{equation}
            \frac{a_i}{L} \leq \frac{1}{2} \frac{\ln(18/13)}{\ln(3/2)} = O(1) \ . 
        \end{equation}


    \item \textbf{The conditional F-threshold $\sigma_{i}^{F|B} < 0$ .}
        By straightforward calculation, we see that $
        \sigma_i^{F|B} = 1 - \frac{c_i^F}{\pr{V_i=1 \mid T_i = B}} = 1 - \frac{\frac{3}{5}p_i}{p_i - p_i'} < 1 - \frac{\frac{3}{5}p_i}{p_i - \frac{1}{2}p_i} = - \frac{1}{5}  
        $.
    
    
    \item \textbf{The P-threshold $\sigma_{i}^{P} = \frac{2}{3}$.} 
        Recall the definition
        \begin{small}
        $$
        c_i^P = \pr{T_i=G} \paren{ \underbrace{  -c_i^F + \pr{V_i=1 \mid T_i = G} \paren{ 1 - \sigma_i^{P} } }_{(a)} }^+ 
        +  \pr{T_i=B} \paren{ \underbrace{ -c_i^F + \pr{V_i=1 \mid T_i = B} \paren{ 1 - \sigma_i^{P} } }_{(b)} }^+ \ . 
        $$
        \end{small}
        If $(a) >0$ and $(b)<0$, it is easy to verify that $ \sigma_i^{P} = \frac{2}{3} $ is indeed implied from the above equation. 
        In what follows, we show that term $(a) >0$ and $(b)<0$ when setting  $ \sigma_i^{P} = \frac{2}{3} $.
        To see this, for $(b)$, we observe that 
        $
        -c_i^F + \pr{V_i=1 \mid T_i = B} \paren{ 1 - \frac{2}{3}} = - \frac{3}{5} p_i + \frac{1}{3} (p_i - p_i') < 0 \ . 
        $
        Next, for term (a): we have 
        \begin{small}
        $$
        -c_i^F + \pr{V_i=1 \mid T_i = G} \paren{ 1 - \frac{2}{3}} 
        = - \frac{3}{5} p_i +  \frac{1}{3} \paren{ \frac{p_i'}{p_i (1-\nu)} + p_i - p_i' }
        = \frac{1}{3} \frac{p_i'}{p_i (1-\nu)} - \frac{4}{15} p_i' - \frac{1}{3} p_i 
        > \frac{1}{3} \frac{1}{2}  - \frac{4}{15} p_i' - \frac{1}{3} p_i \ , 
        $$ 
        \end{small}
        as $p_i' > \frac{1}{2} p_i$ and $ \frac{1}{1-\nu} > 1$. 
        For the right-hand-side to be positive, it suffices to have 
        \begin{equation}
            \frac{4}{15} p_i + \frac{1}{3} p_i' < \frac{4}{15} p_i + \frac{1}{3} p_i < \frac{1}{6}
        \end{equation}
        which translates to $\frac{a_i}{L} = O(1)$, by Equation~\eqref{eq:p_i_to_a_L_ratio}. 
    
    \item \textbf{The F/P threshold $\sigma_{i}^{F/P} > 0$.}
        To prove $\sigma_i^{F/P} > 0$, in view of Theorem~\ref{thm:myopic_stopping}, it suffices to show that the expected payoff of F-opening is greater than the expected payoff of P-opening in the single-box case. 
        The difference of the expected payoff of P-opening and the expected payoff of F-opening is
        \begin{eqnarray}
          && -c_i^P + \pr{T_i = G} \paren{-c_i^F + \pr{V_i=1 \mid T_i=G} \cdot 1 } - \paren{ - c_i^F + \pr{V_i=1} \cdot 1} \nonumber \\ 
            &=& \frac{2}{3} p_i' +  \frac{2}{3}  (1-\nu) p_i (p_i - p_i')  - \frac{2}{5} p_i \label{eq:instance_condition_} \\
            &=& \frac{2}{15} e^{-2  \alpha a_i   } \paren{e^{\frac{1}{2} \alpha a_i   } - 1 } 
            \paren{ \underbrace{ 2 e^{\frac{3}{2}  \alpha a_i  } + e^{ \alpha a_i  } (2-5\nu) - 5(1-\nu) }_{ (*) } } \nonumber  \ . 
        \end{eqnarray}
        Hence, the sign is determined by the $(*)$ term in the last parenthesis. 
        By using $e^x \leq 1+x+x^2$ for $\forall~x\leq 1.79$, we know that whenever
        \begin{equation}  \label{eq:instance_condition_3}
            \frac{a_i}{L} < \frac{1.79}{3} \frac{1}{\ln(\frac{3}{2})} 
        \end{equation}
        for every $i$, we have 
        $
        (*) = 2 e^{\frac{3}{2}  \alpha a_i  } + e^{ \alpha a_i  } (2-5\nu) - 5(1-\nu)
        \leq -1 + 5 (1-\nu) \alpha a_i + ( \frac{13}{2} - 5 \nu ) (\alpha a_i)^2
        $. 
        % $
        % e^{\frac{3}{2}  \alpha a_i  } + e^{ \alpha a_i  } (1-4\nu) - 4(1-\nu) \leq -2 + (\frac{5}{2} - 4 \nu)  \alpha a_i   + (\frac{13}{4} - 4 \nu)  ( \alpha a_i  )^2 \ . 
        % $
        For the latter to be less than $0$, it suffices to impose 
        \begin{equation} \label{eq:instance_condition_4}
            \alpha a_i < \frac{1}{2} \min \braces{ \frac{1 }{5 (1-\nu)} ,\sqrt{\frac{1}{\frac{13}{2} - 5 \nu }}}  \ ,
        \end{equation}
        which again translates to $\frac{a_i}{L} = O(1)$ for every $i$. 
        
\end{enumerate}


\textbf{Second half: the approximated instance. }
In the approximated instance, we use the notation $\hat{\cdot}$ to denote the approximated version of the threshold, obtained by replacing $p_i, p_i'$ with $\hat{p}_i, \hat{p}_i'$ in the calculation. 
We proceed to show that by construction, for the same constant $c \in (0,1)$ prescribed in the first half of the proof, as long as $\delta = \Theta(\frac{1}{L})$, we have 
(1) $\hat{\sigma}_{i}^{F} = \frac{2}{5} $, 
(2) $\hat{\sigma}_{i}^{F|G} > \frac{2}{3} $, 
(3) $\hat{\sigma}_{i}^{F|B} < 0$,
(4) $\hat{\sigma}_{i}^{P} = \frac{2}{3}$,
(5) $\hat{\sigma}_{i}^{F/P} > 0$. 
As a result, there exists an optimal policy that is a committing policy as well in the approximated instance. 

Before calculating the thresholds exhaustively, we make some algebraic observations. 
We recall $\delta \defeq \max_{i \in [n]} ~\max \braces{ \frac{\abs{ p_i - \hat{p}_i }}{p_i} ,  \frac{\abs{ p_i' - \hat{p}_i' }}{p_i'} }  $.
A direct consequence is that 
\begin{equation}
    \abs{p_i - \hat{p}_i} \leq p_i \delta \leq \delta \ . 
\end{equation}
In view of Equation~\ref{eq:consequence_of_jensen_p_p_prime}, we have 
\begin{equation} \label{eq:lower_bound_p_hat_prime_to_p_prime}
    \frac{\hat{p}_i'}{\hat{p}_i} > \frac{(1-\delta) p_i' }{ (1+\delta) p_i } > \frac{1}{2} \frac{1-\delta}{1+\delta}
\end{equation}
as well. 



Moreover, we have  $ \hat{p}_i > \hat{p}_i'$ as long as $\delta = \Theta (\frac{1}{L})$.
To see this, we observe $ \hat{p}_i -  \hat{p}_i' \geq p_i - p_i' - 2 \delta $, and by the Mean Value Theorem, we have 
$
p_i - p_i' = \exp \paren{ - \frac{1}{2} \alpha a_i } - \exp \paren{ - \alpha a_i } = \exp \paren{ \xi} \frac{1}{2} \alpha a_i 
$
for some $\xi$  between $- \frac{1}{2} \alpha a_i$ and $-  \alpha a_i$.
Hence, $\exp \paren{ \xi } \frac{1}{2} \alpha a_i \geq  
\exp \paren{ - \alpha a_i } \frac{1}{2} \alpha a_i 
= \exp \paren{ - \ln(\frac{3}{2}) \frac{a_i}{L-T} } \frac{1}{2} \ln(\frac{3}{2}) \frac{a_i}{L-T}
\geq \exp \paren{ - 2 \ln(\frac{3}{2})  } \frac{1}{2} \ln(\frac{3}{2}) \frac{1}{L}
$, as $\frac{a_i}{L-T} \leq \frac{2a_i}{L} \leq 2$. 
Therefore, in order for 
$$
p_i - p_i' = \exp \paren{ \xi} \frac{1}{2} \alpha a_i  
\geq \exp \paren{ - 2 \ln\frac{3}{2}  } \frac{1}{2} \ln \frac{3}{2} \frac{1}{L} 
> 2 \delta \ , 
$$
it suffices to require 
$$
\delta = \exp \paren{ - 2 \ln\frac{3}{2}  } \frac{1}{4} \ln(\frac{3}{2}) \frac{1}{L} = \Theta \left( \frac{1}{L} \right)  \ .
$$

Now, we turn to the computation of thresholds. 
\begin{enumerate}
    \item \textbf{The F-threshold $\hat{\sigma}_{i}^{F} = \frac{2}{5} $.} 
    Recall the definition $ c_i^F = \E{ \paren{V_i - \sigma_i^F}^+ } = \pr{V_i=1} \paren{1 - \sigma_i^F} $. In the approximated version, $\hat{\sigma}_{i}^{F}$ is the solution to $ \frac{3}{5} \hat{p}_i = \hat{p}_i \cdot \paren{1 - \hat{\sigma}_{i}^{F}}  $, which can be calculated exactly. 
    \item \textbf{The F-threshold $\hat{\sigma}_{i}^{F|G} > \frac{2}{3} $.}  
    Following the same reasoning as Equation~\ref{eq:sigma_F_G_true_hard_instance}, we have 
    $$
        \hat{\sigma}_{i}^{F} = 1 - \frac{3}{5} \frac{\hat{p}_i^2}{ \frac{1}{1-\nu} \hat{p}_i' + \hat{p}_i ( \hat{p}_i - \hat{p}_i') } \ . 
    $$
      Since we ensure $ \hat{p}_i > \hat{p}_i'$ and Inequality~\ref{eq:lower_bound_p_hat_prime_to_p_prime}, we can upper bound
      $$
\frac{\hat{p}_i^2}{ \frac{1}{1-\nu} \hat{p}_i' + \hat{p}_i ( \hat{p}_i - \hat{p}_i') }
< \frac{\hat{p}_i^2}{ \frac{1}{1-\nu} \hat{p}_i' }
< (1-\nu) 2 \frac{1+\delta}{1-\delta} \hat{p}_i
\leq 2 \frac{1+\delta}{1-\delta} (p_i + \delta) \ . 
      $$
      Moreover, $ \frac{1+\delta}{1-\delta} (p_i + \delta) < 2  (p_i + \delta)$ if $\delta < \frac{1}{3}$. 
      Hence, it suffices to impose $p_i < \frac{5}{36} - 0.0001$ and $\delta < 0.0001$ to make sure that $\hat{\sigma}_{i}^{F|G} > \frac{2}{3} $. 

    \item \textbf{The F-threshold $\hat{\sigma}_{i}^{F|B} < 0 $.}   
            For the approximated threshold  $
        \hat{\sigma}_i^{F|B} =  1 - \frac{\frac{3}{5} \hat{p}_i}{\hat{p}_i - \hat{p}_i'} 
        < 1 - \frac{\frac{3}{5} \hat{p}_i}{ \hat{p}_i - \frac{1}{2} \frac{1-\delta}{1+\delta} \hat{p}_i} = 1 - \frac{3}{5} \frac{2+2 \delta}{1+3\delta}
        $. It is easy to verify that $\hat{\sigma}_i^{F|B} < 0$ as long as $\delta < \frac{1}{9}$. 
    \item \textbf{The P-threshold $\hat{\sigma}_{i}^{P} = \frac{2}{3} $.} 
    Recall the definition
        \begin{small}
        $$
        c_i^P = \pr{T_i=G} \paren{ \underbrace{  -c_i^F + \pr{V_i=1 \mid T_i = G} \paren{ 1 - \sigma_i^{P} } }_{(a)} }^+ 
        +  \pr{T_i=B} \paren{ \underbrace{ -c_i^F + \pr{V_i=1 \mid T_i = B} \paren{ 1 - \sigma_i^{P} } }_{(b)} }^+ \ . 
        $$
        \end{small}
        In the approximated instance, when setting $\sigma_i^P = \frac{2}{3}$, it is easy to see $(b) = - \frac{3}{5} \hat{p}_i + \frac{1}{3} (\hat{p}_i - \hat{p}_i') < 0$ as long as $\delta = O(1)$. 
        Likewise, for term (a), we observe that  
    $
\frac{1}{3} \frac{\hat{p}_i'}{\hat{p}_i (1-\nu)} - \frac{4}{15} \hat{p}_i' - \frac{1}{3} \hat{p}_i 
> \frac{1}{3} \frac{1}{2} \frac{1-\delta}{1+\delta} \frac{1}{1-\nu} - \frac{4}{15} \hat{p}_i' - \frac{1}{3} \hat{p}_i
> \frac{1}{3} \frac{1}{2} \frac{1-\delta}{1+\delta}  - \frac{4}{15} (p_i'+\delta) - \frac{1}{3} ( p_i+\delta) . 
    $
    One can verify that the latter is strictly positive as long as $\delta = O(1)$.
    \item \textbf{The F/P-threshold $\hat{\sigma}_{i}^{F/P} > 0 $.} 
    In the approximated version, the difference of the expected payoff of P-opening and the expected payoff of F-opening is
\begin{eqnarray}
  && -c_i^P + \pr{T_i = G} \paren{-c_i^F + \pr{V_i=1 \mid T_i=G} \cdot 1 } - \paren{ - c_i^F + \pr{V_i=1} \cdot 1} \nonumber \\ 
    &=& \frac{2}{3} \hat{p}_i' + \frac{2}{3}  (1-\nu) \hat{p}_i (\hat{p}_i - \hat{p}_i')  - \frac{2}{5} \hat{p}_i \nonumber \label{eq:instance_condition_}  \\ 
    &\leq& \frac{2}{3} (1+\delta) p_i' +  \frac{2}{3}  (1-\nu)  (1+\delta)  p_i ( (1+\delta) p_i - (1-\delta) p_i')  - \frac{2}{5} (1-\delta) p_i \nonumber \\ 
    &\defeq& E(\delta, \nu, \alpha)  \ . 
\end{eqnarray}

    

Recall the fact that $ \frac{x}{1+x} < 1 - e^{-x} < \frac{x+x^2}{1+x+x^2}$ for $-1 < x < 1.79$. 
Moreover, $\frac{x+x^2}{1+x+x^2} = x - x^3 + O(x^4)$ and $\frac{x}{1+x} = x + O(x^2) $.  
We hence have 
$$
  \frac{\alpha a_i}{1+\alpha a_i}   < p_i <   \frac{\alpha a_i + \alpha^2 a_i^2}{1 + \alpha a_i + \alpha^2 a_i^2}
\text{ and }  
\frac{ \frac{1}{2} \alpha a_i}{1+ \frac{1}{2} \alpha a_i}  
< p_i' < 
\frac{ \frac{1}{2} \alpha a_i + \frac{1}{4} \alpha^2 a_i^2}{1 + \alpha a_i + \frac{1}{4} \alpha^2 a_i^2} 
$$
as long as $ \alpha a_i < 1.79$, which translates to the condition $ \frac{a_i}{L} < \frac{1.79}{ \ln(3/2) } = O(1) $.
Therefore, 
\begin{eqnarray*}
    & & E(\delta, \nu, \alpha)  \\ 
    &<& \frac{2}{3} (1+\delta) p_i' +  \frac{2}{3}  (1-\nu)  (1+\delta)  p_i ( (1+\delta) p_i - (1-\delta) p_i')  - \frac{2}{5} (1-\delta) p_i  \\ 
    &<& \frac{2}{3} (1+\delta) \frac{ \frac{1}{2} \alpha a_i + \frac{1}{4} \alpha^2 a_i^2}{1 + \alpha a_i + \frac{1}{4} \alpha^2 a_i^2} \\
    & & +  \frac{2}{3}  (1-\nu)  (1+\delta)  \frac{\alpha a_i + \alpha^2 a_i^2}{1 + \alpha a_i + \alpha^2 a_i^2}
    \paren{ (1+\delta)  \frac{\alpha a_i + \alpha^2 a_i^2}{1 + \alpha a_i + \alpha^2 a_i^2} - (1-\delta) \frac{ \frac{1}{2} \alpha a_i}{1+ \frac{1}{2} \alpha a_i}   }  \\ 
    & & - \frac{2}{5} (1-\delta) \frac{\alpha a_i}{1+\alpha a_i}  \\ 
    &=& \left( - \frac{1}{15} + \frac{11}{15} \delta \right) \alpha a_i + O( \alpha^2 a_i^2) \ . 
\end{eqnarray*}
In order for the latter to be negative, it suffices to impose $\delta < \frac{1}{11}$ and $\alpha a_i = O(1)$. 


\textbf{An optimal policy must be a committing policy.}
We proceed by induction on the number of closed boxes.
\begin{itemize}
    \item Base case: For $n=1$, the claim is immediate.
    \item Assume the statement holds for all well-separated instances of \(n \ge 1\) closed boxes. 
Consider an instance with \(n+1\) closed boxes and let \(\pi^*\) be an optimal policy. 
\(\pi^*\) must either F-open or P-open a closed box:
    \begin{itemize}
      \item \emph{F-open}: If \(\pi^*\) finds a reward, it stops immediately. 
      Otherwise, we transition to a state with \(n\) boxes, where by the inductive hypothesis, a committing policy is optimal.
      \item \emph{P-open}: If the box is good, it would be suboptimal not to F-open it immediately. 
      If it is bad, the box is discarded and does not affect subsequent decisions.
      Either way, we again reach a state with \(n\) boxes, which by the inductive hypothesis admits a committing policy.
    \end{itemize}
In both cases, the policy transitions to a scenario where a committing policy is optimal, so \(\pi^*\) itself must be committing.
\end{itemize}







\end{enumerate}







\end{myproof}






            
            
            
            
The next Lemma shows the parameter $\alpha$ is carefully set so that we can use a Pandora oracle to solve a $\varepsilon$-SSP instance. 


\begin{lemma}
There exists a universal constant $c \in (0,1)$, such that given any instance of $\varepsilon$-SSP where $\varepsilon < c$, the answer to it is YES if and only if the optimal policy for the associated well-separated PSI P-opens a subset $W^*$ that satisfies $T = \sum_{i \in W^*} a_i$.
\end{lemma}
\begin{myproof}
    The ``if" part is obvious, as such a subset $W^*$ is an solution to the SSP. 

    For the ``only if" part, we first note that by construction of the PSI instance and in light of Lemma~\ref{lemma:hard_psi_is_committing},  finding an optimal policy for this PSI instance reduces to identifying an optimal committing policy. 
    Recall $K_i =  \min \braces{V_i, \sigma^F } $, $\tilde{K}_i = \min \braces{ V_i, \sigma^P, \sigma_{i}^{ F | T_i}  }$. 
    For a committing policy $(F,P)$, we define  $ x(P) \defeq \frac{ \sum_{j \in P}^{} a_j }{\sum_{i=1}^{n} a_i} $. 
    Recall $\alpha = \frac{\ln(\frac{3}{2})}{L-T}$. 
    Lemma~\ref{lemma:committing} shows that the expected payoff of a committing policy $(F,P)$ is exactly 
\begin{eqnarray}
 \Psi( x(P)   ) &=&   \E{ 
    \max \braces{ 
    \max_{i \in F} \braces{K_i} ,  
    \max_{j \in P } \braces{ \tilde{K}_j }
    } } \nonumber \\ 
    &=& \sigma^P \cdot 
    \pr{  \max_{j \in P } \braces{ \tilde{K}_j } = \sigma^P  } \nonumber   \\
    && + \sigma^F \cdot 
    \pr{ \max_{i \in F} \braces{K_i} = \sigma^F } 
    \paren{ 1 -  \pr{  \max_{j \in P } \braces{ \tilde{K}_j } = \sigma^P }  }  \nonumber  \\ 
    && +  0 \cdot 
    \pr{ \max_{i \in F} \braces{K_i} = 0 } 
    \pr{  \max_{j \in P } \braces{ \tilde{K}_j } \leq 0}  \nonumber  \\
    &=& \sigma^P  \cdot 
    \paren{ 1 - \prod_{j \in P} \paren{ 1 - p_j' } } 
    + \sigma^F \cdot 
    \paren{ 1 -  \prod_{i \in F } \paren{1-p_i}   }  
    \paren{ \prod_{j \in P} \paren{1- p_j'  }  }  \\
    &=&  \frac{2}{3} \paren{ 1 - \exp \paren{ - \alpha \sum_{ i \in P} \frac{1}{2} a_i  } } 
    + \frac{2}{5}  \paren{ 1 - \exp \paren{  - \alpha \sum_{i \in F} a_i  }  } 
    \exp \paren{ - \alpha \sum_{ i \in P} \frac{1}{2} a_i  }  \nonumber  \\ 
    &=&  \frac{2}{3} \paren{ 1 - \exp \paren{ - \frac{1}{2} \frac{ \ln(\frac{3}{2}) }{ 1 - \frac{T}{\sum_{i=1}^{n} a_i}  } x } } 
    + \frac{2}{5}  \paren{ 1 - \exp \paren{  - \frac{ \ln(\frac{3}{2}) }{ 1 - \frac{T}{\sum_{i=1}^{n} a_i}  } (1-x)  }  } 
    \exp \paren{ - \frac{1}{2}  \frac{ \ln(\frac{3}{2}) }{ 1 - \frac{T}{\sum_{i=1}^{n} a_i}  } x  }  \nonumber \ .  
    % &=&  \frac{1}{6} \paren{  4 - 3^{- \frac{S}{2(S-T)}x  }  - 3^{- \frac{S x - 2 T}{ 2(S-T)  }} } \ , 
\end{eqnarray}
When viewing $\Psi$ as a function defined on $[0,1]$, its derivative is 
$$
\frac{d \Psi}{d x}(x)  = \frac{2}{15} \left(5-e^{-\frac{L x \ln (3)}{2 L-2 T}} \left(3 e^{\frac{L (x-1) \ln (3)}{L-T}}+2\right)\right)  \ . 
$$
% $$
% \frac{d \Psi}{d x}(x) 
% = \frac{L \ln (3) 3^{\frac{2 T-L (x+4)}{2 (L-T)}} 
% \left(3^{\frac{L}{L-T}}-3^{\frac{L x}{L-T}+1}\right)}{4 (L-T)}
% $$
It is easy to verify that this function is unimodal on $[0,1]$, and hence the first-order-condition  $\frac{d \Psi}{d x} = 0$ leads to the optimal solution $x^* = \frac{T}{L}$. 

Suppose the answer to the SSP instance is YES. 
Namely, there exists a partition $W^*$ such that $\sum_{i \in W^*} a_i = T$. 
We can use the PSI oracle to solve the associated PSI instance. 
As there is an optimal policy that is a committing policy, we can read off the partition $(F^*,P^*)$. From the discussion above, we must have $\sum_{i \in P^*} a_i = T = \sum_{i \in W^*} a_i $, as desired. 
\end{myproof}


\paragraph{\bf Polynomial-sized encoding.} 
At this point, the remaining challenge is to prove that the computational effort required to compute the approximated associated PSI instance, such that it retains the same optimal committing policy as the true associated instance, is still polynomial in $n \log( \max_{i \in [n]} a_i )$, which is number of bits required to encode the  original SSP instance.



Given $P \subseteq [n]$, the true expected payoff of a committing policy $(F,P)$ is 
\begin{small}    
$$ 
\Psi(x(P)) = \E{ 
    \max \braces{ 
    \max_{i \in F} \braces{K_i} ,  
    \max_{j \in P } \braces{ \tilde{K}_j }
    } } 
    = \sigma^P  \cdot 
    \paren{ 1 - \prod_{j \in P} \paren{ 1 - p_j' } } 
    + \sigma^F \cdot 
    \paren{ 1 -  \prod_{i \in F } \paren{1-p_i}   }  
    \paren{ \prod_{j \in P} \paren{1- p_j'  }  } \ . 
$$
\end{small}

In the reduction, instead of computing exactly $p_i, p_i'$'s, we can only afford to compute the approximated inputs $\hat{p}_i, \hat{p}_i'$'s and feed them to the PSI oracle. Hence, the approximated expected payoff function is 
\begin{equation}
    \widehat{\Psi} ( P ) = \sigma^P  \cdot 
    \paren{ 1 - \prod_{j \in P} \paren{ 1 - \hat{p}_j' } } 
    + \sigma^F \cdot 
    \paren{ 1 -  \prod_{i \in F } \paren{1- \hat{p}_i}   }  
    \paren{ \prod_{j \in P} \paren{1- \hat{p}_j'  }  }  \ . 
\end{equation}
Hence, we are able to characterize the approximation error $\abs{ \Psi(x(P)) - \widehat{\Psi}(P) }$ in terms of the encoding precision $\delta$. 
\begin{claim}  \label{lemma:obj_truncation_error}
    For all $P \subseteq [n]$, $ \abs{ \Psi(x(P)) - \widehat{\Psi}(P) } \leq (\sigma^P + \sigma^F) \cdot \paren{ n \delta }$.   
    % O\paren{n \frac{ ( 2 \ln(3) \varepsilon)^k}{k!}}$.   \cdot \paren{ \max_{i \in [n] } \braces{ p_i' - \hat{p}_i' + p_i - \hat{p}_i  } }
\end{claim}

\begin{myproof}
    
Given fixed set $P \in 2^{[n]}$, consider the following function $f: [0,1]^n \rightarrow \mathbb{R}$
$$
f( \bfx ) = \sigma^P \cdot \paren{ 1 - \prod_{j \in P}  (1-x_j) } + \sigma^F \cdot \paren{  1 - \prod_{j \in [n] \setminus P } (1-x_j)  } \paren{  \prod_{j \in P} (1-x_j) } \ , 
$$
where $\bfx$ denotes a $n$-dimensional vector and $x_j$ is the $j$-th element of it. 
Its partial derivative with respect the $i$th element is 
\begin{eqnarray*}
    \frac{\partial f}{ \partial x_i } &=& \one{ i \in P  }  \brackets{
    \sigma^P \cdot \prod_{ j \in P \setminus \{ i \} } (1-x_j) 
    + (- \sigma^F ) \cdot \paren{ 1 - \prod_{j \in [n] \setminus P} (1-x_j) } \paren{ \prod_{ j \in P \setminus  \{ i \} } (1-x_j) } 
    }  \\ 
    && + \one{ i \in [n] \setminus P } \brackets{ \sigma^F \cdot \paren{ \prod_{ j \in P} (1-x_j) } \paren{ \prod_{ j \in [n] \setminus ( P \cup \{i\} )    }  (1-x_j) }   }    \ . 
\end{eqnarray*}
It is easy to see that $\abs{ \frac{\partial f}{ \partial x_i }(\bfx) } \leq \sigma^P + \sigma^F $ for $ \bfx \in [0,1]^n$. 
When we calculate $\hat{p}_i, \hat{p}_i$'s, we can easily keep them in the range of $[0,1]$. 
Therefore, applying Mean Value Theorem yields that 
$$
\abs{ \Psi(x(P)) - \widehat{\Psi}(P) } \leq 
(\sigma^P + \sigma^F) \cdot \abs{ \sum_{ j \in P  } ( p_j' - \hat{p}_j' )   +  \sum_{ j \in [n] \setminus P } ( p_j - \hat{p}_j )  } 
\leq (\sigma^P + \sigma^F) \paren{n \delta }  \ . 
$$
We note that the above argument works for any fixed $P$. The proof is hence complete. 

\end{myproof}




Moreover, the function $\Psi$ has enough curvature at the point $\frac{T}{L}$. 
\begin{claim} \label{lemma:curvature}
For any $0 \leq T \leq \frac{L}{2}$, where $L \geq 2$, 
    $
     \Psi(\frac{T}{L}) - \Psi( \frac{T}{L}  + \frac{1}{L} )  \geq  (\frac{\ln(3)}{2})^2 3^{-3} \frac{1}{L^2}
     % \bigOmega{ \frac{1}{L^2} } 
    $
    and 
    $
    \Psi(\frac{T}{L}) - \Psi( \frac{T}{L} - \frac{1}{L} )  \geq (\frac{\ln(3)}{2})^2 3^{-3} \frac{1}{L^2} \ . 
    % \bigOmega{ \frac{1}{L^2} } \ .
    $
\end{claim}

\begin{myproof}
We only prove the first inequality. The second can be handled similarly. 
When viewing $\Psi$ as a function defined on $[0,1]$,
\begin{small}
\begin{eqnarray*}
  \Psi(x)  &=&  \frac{2}{3} \paren{ 1 - \exp \paren{ - \frac{1}{2} \ln(3)  \frac{L}{ L-T }  x   } }  + \frac{1}{2}  \paren{ 1 - \exp \paren{  - \ln(3) \frac{L}{L-T} \paren{1-x}     }  } 
    \exp \paren{ - \frac{1}{2} \ln(3)  \frac{L}{L-T} x  }  \ .  \nonumber 
\end{eqnarray*}
\end{small}
As it is smooth enough, by Taylor's expansion, we have 
$$
\Psi \paren{ \frac{T}{L}   + \frac{1}{L} } 
= \Psi \paren{ \frac{T}{L} } + \underbrace{\Psi' \paren{ \frac{T}{L} }}_{=0}   \frac{1}{L} + \frac{1}{2} \Psi'' \paren{ \xi } \paren{\frac{ 1 }{ L }}^2  \ ,
$$
for some $\xi$ on the line segment of $ \frac{T  \pm 1}{L} $ and $\frac{T}{L}$. 
In what follows, we proceed to lower bound $ \abs{\Psi'' \paren{ \xi }} $. To straightforward calculation, we have 
$$
\Psi''(x) = -  \frac{ \ln(3)^2 }{8} \cdot (\frac{L}{L-T})^2 \cdot  3^{\frac{L (x-4)+2 T}{2 (L-T)}} \cdot \paren{ 3^{\frac{L-L x}{L-T}}+3 } \ . 
$$
By noting that for any $x \in [0,1]$ and $0 \leq T \leq \frac{L}{2}$: 
\begin{itemize}
    \item $3^{\frac{L-L x}{L-T}} \geq 3^0 = 1$,
    \item $3^{\frac{L (x-4)+2 T}{2 (L-T)}} \geq 3^{\frac{-4 L +2 T}{2 (L-T)}} = 3^{\frac{-2 L +T}{L-T}} \geq 3^{-3}$,
    \item $\frac{L}{L-T} \geq 1$,
\end{itemize}
we conclude that $
\abs{ \Psi''(x) } \geq (\frac{L}{L-T})^2 \frac{4 \ln(3)^2}{8} 3^{-3}  
\geq \frac{ \ln(3)^2}{2} 3^{-3} 
$
for any $x \in [0,1]$ and $0 \leq T \leq \frac{L}{2}$. 


\end{myproof}

Combining Lemma~\ref{lemma:obj_truncation_error} and Lemma~\ref{lemma:curvature}, we have a chain of inequalities
$$
\hat{\Psi} \paren{ \frac{T}{L} } \geq \Psi \paren{ \frac{T}{L} } - O \paren{ n \delta } 
\geq  \Psi \paren{ \frac{T  \pm 1}{L} } +  \bigOmega{ \frac{1}{L^2} } - O \paren{ n \delta }  
\geq \hat{\Psi} \paren{ \frac{T  \pm 1}{L} }   +  \bigOmega{ \frac{1}{L^2} } - O \paren{ n \delta }   \ . 
$$
Therefore, it suffices to make $\delta$ small enough so that $\bigOmega{ \frac{1}{L^2} } \geq O \paren{ n \delta }  $ to make $ \hat{\Psi} \paren{ \frac{T}{L} } \geq \hat{\Psi} \paren{ \frac{T  \pm 1}{L} }$. 
In addition,  we note that it is easy to show  $\hat{\Psi}$ is unimodal as a function defined on $[0,1]$. 
Hence, when viewed as functions on subsets, both $\hat{\Psi}$ and $\Psi$ will attain the global maximum at the same subset. 


Lastly, we conclude that the polynomial-sized encoding is feasible, by virtue of the following classic result (stated in our context). 
\begin{lemma}[\cite{brent1976fast}]
    Assuming access to multitape Turing machine, let $M(d)$ be the number of bit-operations required to multiply $d$-bit numbers with $d$-bit accuracy.  
    It takes $O(\log(d) M(d))$  bit operations to ensure that $\max \braces{ \frac{\abs{p_i - \hat{p}_i}}{p_i} ,  \frac{\abs{p_i'- \hat{p}_i'}}{p_i'}}  \leq 2^{-d}$
    for each $i$, for the parameter $\alpha = \frac{\ln(\frac{3}{2})}{L-T}$. 
\end{lemma}

\begin{remark}[Relation to \cite{fu2022pandora}]
\label{remark:connections_to_fu}
    At their core, both \cite{fu2022pandora} and our work study variations of the Pandora's box problem: one problem with non-obligatory inspections, and another where there are two types of inspections and where one type must be followed by the other type prior to selection. 
    Both hardness proofs are based on restricted problem instances for which different notion of ``committing policies" are optimal. 
    Both proofs use reductions to the Subset Sum problem \citep[][use the Partition problem, a special case of the Subset Sum problem]{fu2022pandora}.

    However, the proofs also differ along multiple dimensions. 
\begin{enumerate}
    \item 
    The combinatorial hardness in the two problems stems from different sources: ordering $n!$ potential permutations of boxes \citep{fu2022pandora} versus choosing one of $2^n$ inspection modes for the boxes.
    
    
    To clarify, in \cite{fu2022pandora},  the hardness comes \textit{solely} from deciding the ordering $\sigma$ of the boxes. 
    The support set of the value of boxes is $\{ 0, \frac{1}{2}, 1\}$ (the three-point support is essential, as the problem admits a polynomial-time computable optimal policy if the distributions are only supported on $\{ 0, 1 \}$).
    The optimal policy inspects boxes according to the order $\sigma$. Whenever it sees the value $1$, it selects the box immediately. 
    Whenever it sees the value $\frac{1}{2}$, it runs Weitzman's index policy on the remaining boxes, without using the option to select a box without inspection. 
    If it never sees the value $\frac{1}{2}$ and reaches the last box, then it exercises the option to select without inspection. 

    For a given instance of Partition with $n$ items, they construct the hard instance by introducing two  auxiliary boxes $B_{n+1}$ and $B_{n+2}$. 
    The construction ensures that $B_{n+2}$ optimally appears in the last position of the ordering, and is therefore the only box that may be selected without inspection. 
    The computational difficulty lies in determining the position of $B_{n+1}$ in the permutation: the optimal placement induces a partition of the remaining boxes into two segments with equal total weights, whenever such a partition exists. 

    By contrast, in our hard instance, the support set of the value of boxes is $\{0,1\}$. 
    Our instance is carefully crafted so that a committing policy is optimal. 
    The combinatorial decision is therefore not an ordering problem, but rather the choice between full (F) versus partial (P) inspection for each box. Once the inspection modes are fixed, the remaining ordering decision is straightforward. 
    
    \item In both cases, constructing the hard instance relies on a deep structural characterization of optimal policies, which makes it possible to explicitly derive the analytical form of the expected payoff as a function of the underlying combinatorial decision. 
    Namely, the inspection ordering in \cite{fu2022pandora} and the choice between full versus partial inspection in our setting.
    Building on insights from \cite{guha2008information}, \cite{fu2022pandora} strengthen the characterization of optimal policies and exploit this structure in their hardness construction. 
    In contrast, our reduction builds on the structural results established in our paper, e.g., Theorems~\ref{thm:myopic_stopping} and~\ref{thm:just_strong}, which characterize optimal behavior under obligatory inspection and sequential opening modes.
    
    \item There are also several technical differences between the two hardness constructions. For instance, \cite{fu2022pandora} design their instances so that all primitives lie on a finite grid of rational numbers. In contrast, to facilitate multiplicative computations, we parameterize the Bernoulli probabilities in exponential form, which results in primitives that are no longer confined to a finite rational grid. Accordingly, we provide a careful discussion of the encoding length required to represent our problem instances.  
    Moreover, in their construction, boxes have heterogeneous opening thresholds. In our instance, by contrast, the full-inspection (F) and partial-inspection (P) thresholds are identical across boxes (at least in the true instance of the reduction). 
    
    
\end{enumerate}
\end{remark}