
\section{Problem Formulation}   \label{sec:formulation}

Pandora (the decision-maker) is given $N \in \mathbb{N}^*§$ boxes containing random prizes. Each box $i \in [N]$ is associated with a priori unknown prize $V_i$ and type $T_i$  drawn from a known joint probability distribution $\mathcal{D}_i$. We assume that $V_i$ is either a continuous or discrete scalar random variable and that $T_i$ is a discrete scalar random variable with support $\Gamma_i$.\endnote{Throughout, we use capital letters to denote random variables and lowercase letters to denote their realizations.}
We assume that the support of $\mathcal{D}_i$ is contained in $\mathbb{R}^+  \times \Gamma_i$, and that the random variables $(V_1,T_1),\ldots,(V_N,T_N)$ are mutually independent (for each box $i$, the random variables $V_i$ and $T_i$  are dependent; otherwise the type would not be informative about the prize).
Pandora can open a box in one of two inspection modes: full opening (F-opening) and partial opening (P-opening).
The realization of type $T_i$ is revealed immediately by P-opening box $i \in [N]$, while the corresponding F-opening action reveals the realization of $(V_i,T_i)$.
These opening actions incur constant costs, respectively denoted by $c_i^F$ and $c_i^P$, which are also known to Pandora.% and satisfy $c_i^F > c_i^P > 0$.



% \vspace{-0.3in}
Figure~\ref{fig:states_diagram} illustrates the state evolution of each box following various actions.
We call the initial state of a box \textit{closed}; here, the realizations of $V_i$ and $T_i$ are unknown.
 P-opening a closed box changes its state to \textit{partially open}. In this case, Pandora observes the realization of $T_i$, which we denote by $t_i \in \Gamma_i$, and going forward, she updates her belief about $V_i$ to the conditional distribution $\operatorname{Pr}[V_i \in \cdot \mid T_i = t_i]$. We sometimes refer to this conditional distribution as $V_i  \mid  t_i$ for short. We say that a box is \textit{fully open} once F-opening takes place. Here, Pandora observes the realizations of $V_i$ and $T_i$, which we denote by $v_i, t_i$, respectively.
Lastly, the problem terminates when a fully open box is selected.
We note that full opening is a prerequisite for selection in a way similar to the standard Pandora's box problem.
The state of the system is jointly described by the collective individual state of all boxes.


An adaptive policy in our generalized Pandora's box problem is a mapping between system states and feasible actions. There are three types of  feasible actions: (1) P-opening a closed box, (2) F-opening a closed or partially open box, and (3) selecting a fully open box.
Alternatively, this can be seen as a cascade process of (1) deciding whether to select a box (stop) or keep inspecting (continue), (2) choosing a box to inspect, and (3) deciding on a box-opening mode. Our goal is to develop a policy that maximizes the expected profit, defined as the selected prize minus the box-opening costs.



% \vspace{-0.1in}

% \vspace{-0.1in}
\subsection{Dynamic programming (DP) formulation}
The problem naturally lends itself to a DP formulation. While the state space is exponentially large (and therefore, the DP cannot be approached using standard solution methods), we exploit this formulation to derive structural properties of the optimal policy.

\textit{State space.}
Each state of the DP can be described by a tuple $(\mathcal{C}, \mathcal{P}, y)$, where $\mathcal{C} \subseteq [N]$ is the set of closed boxes,
$\mathcal{P}$ is formed by all pairs $(i,t_i)$, describing each P-opened box $i$ and its corresponding type $t_i$ (revealed by P-opening), and
$y$ is the maximal prize found so far (it is easy to see that all fully open boxes whose prize is smaller than $y$ can be discarded, since at most one prize can be claimed).
We observe that the total number of states is at least $\prod_{i=1}^{N}\left( 1+ \mid \Gamma_i \mid  \right)$, which is exponentially large. 


\textit{Actions.}
At each state $(\mathcal{C}, \mathcal{P}, y)$, we can fully open a closed or partially open box,  partially open a closed box, or select a fully open box and stop.
After F-opening a box $i \in \mathcal{C}$ and observing the realization $v_i$ of its prize $V_i$, we transition to state $(\mathcal{C} \setminus \{i\}, \mathcal{P}, \max \{y, v_i\})$. 
Hereinafter, we slightly abuse the notation by using $i \in \mathcal{P} $ in place of $(i,t_i) \in  \mathcal{P} $.
If we choose to F-open a box $i \in \mathcal{P}$, we transition to state $(\mathcal{C}, \mathcal{P} \setminus \{(i,t_i)\}, \max\{y, v_i \})$, where $v_i$ is the realization of $V_i|t_i$ revealed by our action.
Likewise, if we choose to P-open a box $i \in \mathcal{C}$, we transition to state $(\mathcal{C} \setminus \{i\}, \mathcal{P} \cup  \{(i,t_i)\}, y)$, where  $t_i$ is the type realization of $T_i$ revealed by P-opening box $i$.
Finally, when we select the fully open box whose value is equal to $y$, the decision process terminates.

\textit{Bellman's Equation.}
Let $J(\mathcal{C}, \mathcal{P}, y)$ denote the value function in state $(\mathcal{C}, \mathcal{P}, y)$ under an optimal policy.
Then, $J(\mathcal{C}, \mathcal{P}, y)$ satisfies the Bellman's Equation:
\begin{eqnarray}
J(\mathcal{C}, \mathcal{P}, y) &=& \max \left\{
    \begin{array}{ll}
    y    & \text{select (stop)}     \\
    -c_i^F+ \mathbb{E}_{V_i} \left[J(\mathcal{C} \setminus \{i\}, \mathcal{P}, \max\{V_i, y  \}   ) \right]   & \text{F-open box }    i \in \mathcal{C}    \\
    -c_i^F+   \mathbb{E}_{V_i \mid T_i=t_i} \left[J(\mathcal{C}, \mathcal{P} \setminus \{(i,t_i)\}, \max\{V_i, y  \}   ) \right]  &\text{F-open box }  i \in \mathcal{P}    \\
    -c_i^P+ \mathbb{E}_{T_i} \left[J  \left(\mathcal{C} \setminus  \{i\}, \mathcal{P} \cup \{ (i,T_i)\} , y \right)  \right] & \text{P-open box }  i \in \mathcal{C}
      \end{array}
      \right. \label{eq:Bellman_Equation}
      \\
J(\emptyset, \emptyset, y) &=& y.   \nonumber
\end{eqnarray}
In what follows, we use the shorthand $s_0 = ([N],\emptyset,0)$ to designate the initial system state.

\textit{Policies.}
A feasible policy  $\pi$  is a mapping from each state to a corresponding action, which is selected amongst all those that are feasible in the state in question.  For simplicity, we assume that there exists a unique optimal policy that satisfies Bellman's Equation.


\subsection{Illustrative examples} \label{subsec:motivating_examples}

To provide some intuition about why P-opening could be beneficial, consider the following simple examples.
\begin{example} 
There is a large number of i.i.d. boxes; each contains a prize of 110 with probability $\frac{1}{2}$ and zero otherwise. The box-opening costs are $c_i^F = 100$ and $c_i^P = \epsilon $, and P-opening acquires the same information as F-opening (nevertheless, F-opening is still required  to collect the prize). It is easy to see that given only the  F-opening inspection mode, it is not worthwhile to F-open any box and the expected profit of any policy that opens boxes is negative. However, given the option to P-open, one could identify a box that contains the prize prior to F-opening it. In that case, the expected profit is $110-100=10$  minus $\epsilon$ times the expected number of opened boxes, which is equal to two.
\end{example}


This example shows how the option to P-open could transform a problem where opening boxes is not worthwhile into one in which it is. Hence, the optimality gap for the naive policy that ignores P-opening (i.e., Weitzman's policy, which is a natural candidate for Pandora's box-like problems) is unbounded. 


\begin{example}  \label{example:not_indexable}
Consider the state $(\{ 1 \}, \emptyset, y)$ where there is one box left with two types: `exceptional' and `average,' which can be revealed by P-opening. 
Box 1 is `exceptional' with probability $\delta = 0.01$ and is `average' with probability $1-\delta$. 
If the box is exceptional,  the prize is known to be $2$ almost surely, but if it is average, the prize is uniformly distributed in $[0,1]$. 
Assuming that the F-opening cost is $c_1^F=\frac{1}{3}$ and the P-opening cost is $c_1^P=\frac{1}{3} \delta $, 
it can be easily seen that when $y=0$, both inspection modes are preferred over stopping (which yields $0$). Moreover, F-opening dominates P-opening because F-opening is inevitable in this case. 
However, when $y=1$, F-opening would be no longer worthwhile compared to stopping, because the cost $c_1^F = \frac{1}{3}$ exceeds the expected gain $ \delta \cdot (2 - y) = \delta$. 
By contrast, P-opening (followed by the F-opening) of an exceptional box is advantageous because the expected cost is $c_1^P + \delta c_1^F = \frac{1}{3}\delta + \frac{1}{3}\delta =\frac{2}{3} \delta$, whereas the expected gain is $\delta$.
\end{example}


Intuitively, in the context of job hiring, the instance captures a candidate who is likely `average' but has a small chance of being `exceptional.' A low-cost online interview can reveal this. If no good candidate has been found ($y = 0$), it is optimal to proceed directly with an onsite interview. However, if a strong candidate has already been identified ($y = 1$), the onsite visit should be reserved for an `exceptional' applicant, identified via a relatively short online screening.

Technically, the example shows that the optimal policy is not indexable. If it were, each action would receive a fixed index, and the best action---corresponding to the highest index---would be independent of $y$, which is not the case in Example~\ref{example:not_indexable}. In MAB terms, the optimal activation of one arm depends on the state of others. This illustrates the added complexity of bandit superprocesses, which do not inherit the indexability of classic MABs (see also Section~\ref{sec:literature}).

