

\section{Introduction}
\label{sec:introduction}

Sequential search problems refer to a class of optimization problems that have long been studied in the economics, operations research (OR), and computer science (CS) literature.
In his seminal work, \citet{weitzman1979optimal} studies the Pandora's box sequential search  problem,\endnote{We refer to this model as the \textit{standard Pandora's problem.}} in which Pandora is given a collection of boxes containing random prizes drawn from known and independent probability distributions.
She can adaptively pay box-dependent fees to open boxes and observe their realizations until she decides to select the prize held within one of the open boxes, or stop exploring without selecting any box. Her objective is to maximize the expected profit, that is, the expected value of the collected prize minus the expected combined box-opening fees. This fundamental model, which captures an agent's search for the best alternative, found applications in consumer search, project management, job recruitment, and asset-selling problems, to name a few.


In this paper, we consider a generalization of this problem in which Pandora can also exercise a cheaper and possibly less accurate option of {\em partially opening} boxes.
When partially opening a box, Pandora observes its {\em type}, an informative signal based on which she updates her belief about the prize inside the box.
We refer to this variant as \textit{Pandora's Box with Sequential Inspection} (PSI for short).
Similarly to the standard problem, she may only select a prize contained in a box that was {\em fully opened}, that is, a box whose exact prize has been observed.
However, the ability to partially open boxes introduces a new tradeoff. On the one hand, partially opening a box reveals certain  information about the prize value that allows Pandora to potentially detect ``bad outcomes'' at a lower cost, and thus, avoid paying the full opening fee. On the other hand, while the cost of  partial opening is cheaper than the cost of full opening, it may not be negligible, in which case overusing the option to partially open may lead to excessive costs.

To put this model in concrete terms, consider  job recruitment, an application discussed in~\citet{weitzman1979optimal}.  
Recent technological advances transform job recruitment processes in various industries.
For example,  video conferencing is often used for remote (offsite) interviews.  More recently, AI systems have been  introduced to conduct such initial remote interviews without human intervention; the transcriptions are then reviewed by human evaluators. Remote interviews provide convenient ways for companies to learn more about candidates at reduced costs, compared with onsite interviews. Nevertheless,  remote interviews cannot fully replace onsite visits, which are often still necessary to  eventually make job offers.
Moreover, while cheaper than onsite visits, substantive remote interviews -- beyond the preliminary screenings based on CVs -- still require time from human interviewers or evaluators to  assess the candidates' fit for the position. In selecting a candidate for a vacant position, companies must therefore decide how to synthesize the different mediums to identify and select qualified candidates while minimizing costs.
Put into the framework of our model, Pandora represents the company, boxes correspond to candidates whose prior evaluations are based on screenings and automated assessments, and box opening actions correspond to conducting interviews -- offsite or onsite. The goal is to effectively administer the hiring process by deciding which candidates should be interviewed and in which format: cheaper and less accurate offsite interviews, or more expensive and informative onsite visits. 

More generally and beyond the particular application, our work tries to study how to integrate different \textit{sequential information acquisition} methods in the context of stochastic optimization problems. To our knowledge, this is the first work that examines this feature, which is quite common in various practical sequential search problems (a more detailed discussion can be found in Section~\ref{sec:literature} that surveys related work).

\citet{weitzman1979optimal} showed that there exist optimal policies to the standard Pandora's problem that admit an elegant and simple threshold-based structure. A threshold is defined for each box, indicating the order in which boxes should be considered for opening, reducing the problem to an optimal stopping time problem. The decision about when to stop is determined using the same thresholds by comparing the largest prize amongst open boxes to the largest threshold amongst closed boxes; if the incumbent prize is larger, Pandora should stop; otherwise, she should proceed to the next box, and so forth.
However, it has been observed in the literature (see Section~\ref{sec:literature}) 
that seemingly small changes in the model assumptions break the structure of the optimal policy and lead to problems whose optimal solution cannot be analytically characterized.
Our goal is to study this fundamental sequential search process when partial information acquisition is possible. 
Specifically, we strive to answer the following questions: How should partial opening and full opening be prioritized? Could threshold-based policies, in the same vein as those defined in the standard Pandora's box problem, describe the optimal policy in settings with sequential inspections?  Beyond the characterization of optimal policies, we are also interested in developing simple and intuitive policies with provably good performance guarantees.




\subsection{Results and contributions}
We summarize below the main findings and contributions of our work.

\textit{Modeling.}
    We introduce a new model for sequential search by an agent, which incorporates sequential information acquisition into stochastic optimization problems. %  (also known as probing, testing, and triaging).
    Such information acquisition process can be represented by a directed acyclic graph describing the information states of each box (see Figure~\ref{fig:states_diagram}).
    Our graph layout is unique in that boxes can be inspected repeatedly and there is more than one way to inspect boxes. 
    To our knowledge, this generalized graph layout has not been previously studied.
    Moreover, it raises a fundamental technical challenge, which has been a long-lasting open question in the literature (we further discuss this in Section~\ref{sec:literature}).
    
    \textit{Hardness.} We prove that computing optimal policies for PSI is NP-hard, contrary to the standard Pandora's box problem. The proof is based on a reduction defined using PSI instances that consist of boxes with binary prizes and where partial opening indicates one of two types. 
    

    \textit{Characterization of an optimal policy.} 
    Despite the hardness result, we identify threshold-based rules that almost fully describe the optimal policies.  Similarly to the Pandora's box problem, one type of threshold is associated with decisions to fully open boxes. To capture the added value of partial inspections, we define two additional types of thresholds associated with decisions to partially open boxes.     
    We show that, in most cases, the optimal actions can be prescribed using the newly defined thresholds. In particular, we characterize the optimal stopping criterion (i.e., when to stop searching and collect the best prize presently available), and identify sufficient conditions under which it is optimal to fully or partially open a box. 
    We identify special non-trivial cases where our characterization fully describes an optimal policy, and show that a simple policy, which is defined using these thresholds, is asymptotically optimal. 
    Numerical experiments show that optimal actions are identified by our theoretical characterization in more than 92\% of all systems states, on average, and this percentage increases in the number of boxes of the problem instance.
    


    \textit{Simple robust policies.} Next, we focus on the class of \textit{committing policies}.\endnote{Our approach is inspired by the class of committing algorithms studied by~\cite{beyhaghi2019pandora}, with the notable difference that our setting involves sequential inspections.} These semi-adaptive policies specify a priori whether each box should be partially or fully opened the first time it is inspected. Interestingly, each committing policy induces a corresponding multi-armed bandit problem (MAB) in which the optimal indices coincide with our proposed thresholds. 
    By leveraging fundamental results on the adaptivity gap of stochastic submodular optimization problems, we argue 
    that the optimal a committing policy can be efficiently approximated within a ratio of $1-1/e$.







\textit{Numerical experiments.} We conduct extensive numerical experiments to evaluate the performance of various policies on a diverse set of synthetic instances and obtain additional insights about the optimal policy:

\begin{itemize}
    \item Solving the problem to optimality using exact dynamic programming methods is computationally prohibitive, even when the number of boxes is around 10, the prize distributions have a small support, and the number of types is small. These computational challenges warrant the development of simple suboptimal policies. 

    \item    The number of times an optimal policy exercises the partial opening option increases as (i) there are more boxes, (ii) the partial opening thresholds tend to be larger than the corresponding full opening thresholds, and (iii) the distributions of the prizes are similar across boxes. In contrast, when boxes tend to be different, much about the order by which boxes are inspected is determined without partial opening. 
    
    \item The newly introduced thresholds are key to the development of effective policies. Specifically, the class of committing policies, which utilize our thresholds, achieves a robust performance. In particular, the best committing policy is very close to the optimum, both in terms of average and worst-case performance. In line with the asymptotic analysis, we observe that an intuitive threshold-based committing policy\endnote{Here, the policy commits to partial opening vs. full opening simply by comparing the corresponding thresholds for each box. } is near-optimal when the number of boxes is sufficiently large. 

    
\end{itemize}





Our proofs combine several methods used in recent literature, including sample path coupling and interchange arguments \citep{attias2017stochastic}, reductions to submodular maximization problems \citep{beyhaghi2019pandora}, and results based on the information relaxation duality approach \citep{balseiro2019approximations}.
In this context, our main technical contribution lies in analyzing threshold-based rules using coupling arguments. We also reveal an unnoticed connection between approximation methods independently proposed in the literature. Specifically, we show that the cost accounting technique of \cite{beyhaghi2019pandora} amounts to a relaxation of Whittle's integral, a more general upper bound for multi-armed bandit superprocesses.

    

Overall, our results suggest that generalized Weitzman's thresholds play an important role in characterizing  both optimal and near-optimal inspection and selection decisions when the decision-maker can sequentially inspect boxes. This aspect of selection processes has not been thoroughly studied in previous literature, as we discuss next. 





\subsection{Related Work} \label{sec:literature}

Our work relates to several streams of literature in economics, operations research, and computer science. 
We divide them imperfectly into three parts: generalization of the standard problem, Markovian MAB problems, and applications of sequential search.

\textit{The Pandora's box problem and its variants.} 
    The seminal work of \cite{weitzman1979optimal} led to substantial research on more general and realistic settings. 
    For example, \cite{vishwanath1992parallel} consider a generalization with parallel searches, where Pandora can open several boxes simultaneously at a discounted cost. The authors identify distributional assumptions under which it is optimal to open boxes according to Weitzman's thresholds.    
    \cite{olszewski2015more} examine a generalization where the objective function depends on all discovered prizes.\endnote{In the standard Pandora's box problem, the objective function is simply the maximum observed prize.}  They show that if a threshold-based rule is unconditionally optimal, then the problem is reducible to the standard Pandora's box setting.
    \cite{boodaghians2020pandora} study a variant of the Pandora's box problem in which precedence constraints are imposed on the inspections of boxes. They show that when the precedence constraints are tree-shaped, the optimal policy can still be described as a threshold-based rule.
    {  
    \cite{gibbard2022model} extend the Pandora's box problem by assuming that the prize is additive and that a two-step sequential inspection reveals the exact value of each part. Conceptually, such a model studies how information acquisition should be prioritized when the acquisition process can be broken into multiple steps. The model is a special case of the MAB problem \citep{bertsimas1996conservation} that inherits the indexability structure of the optimal policy. 
    In contrast, our model attempts to capture a different tradeoff between two information acquisition methods (a cheaper and less precise versus a more expensive and accurate), a characteristic which we show to be challenging analytically and computationally.
    }
    
    Recently, there has been a growing interest in non-obligatory inspections~\citep{attias2017stochastic, doval2018whether,beyhaghi2019pandora} where Pandora may select any closed box without inspecting it (in which case the prize is random at selection). Building on a clever cost accounting method, \cite{beyhaghi2019pandora} show that this setting is a special case of maximizing a stochastic non-negative submodular function under a matroid constraint, a breakthrough that paved the way to the design of approximation algorithms. Our algorithmic results in Section~\ref{sec:apx} draw from this line of reasoning. Closer to our work, \cite{beyhaghi2019approximately} studies a setting in which Pandora can choose from multiple opening actions for each box. However, unlike our work, the search process in that scenario does not feature the notion of sequential inspections. Therefore, such a model does not capture the key tradeoff which we aim to study  between reducing uncertainty significantly at a higher cost, and reducing it only partially at a lower cost with an option to further reduce the uncertainty later at an overall higher cost. This very tradeoff is present in the applications that motivate our work.   
    Finally, we note the work of \cite{clarkson2020fast} that study a problem where an object is hidden at one of several locations according to some known distribution. The goal is to find it in the minimum expected number of attempts using two modes of inspection, fast or slow. This can be seen as a variant of the Pandora's box problem, where the reward is binary, and boxes are correlated and can be inspected indefinitely.
    



\textit{Markovian multi-armed bandits.}
     From a technical perspective, the standard Pandora's box problem is a special case of the Markovian MAB \citep{Gittins1979Bandit}, in which an agent sequentially activates (pulls) one out of many bandits (arms). Arms correspond to independent Markov reward processes, which generate a reward and transition to a new state upon activation. The optimal solution admits an index structure, known as the Gittins index\endnote{Gittins indices and thresholds in Weitzman's policy are equivalent in the special case of the Pandora's box problem \citep[see, e.g., an early version of ][]{olszewski2015more}.}, where every state of every bandit is associated with an index, and it is always optimal to activate the arm whose current state's index is maximal. However, the optimality of the Gittins index breaks under small variations of the model assumptions, such as correlated arms \citep{pandey2007multi}, switching costs      \citep{asawa1996multi}, %\citep{banks1994switching,asawa1996multi}, 
     or delayed feedback \citep{eick1988gittins}. We similarly observe that index policies are  suboptimal in our setting (see Example \ref{example:not_indexable} in Section~\ref{subsec:motivating_examples}).
    
    
    The problem considered in our paper can be  viewed as a special case of MAB superprocesses \citep{gittins2011multi}, in which there exist multiple ways to pull each arm. That is, after an arm is selected, one has to choose the mode of activation, which affects transitions and rewards. General knowledge about this class of problems is rather limited. 
    Unlike the standard MAB problem, MAB superprocesses need not admit an optimal index policy.
    Much of the existing literature explores special cases where index policies are ``unambiguously'' optimal~\citep{whittle1980multi}, as well as heuristic solution methods and upper bounds~\citep{brown2013optimal,balseiro2019approximations}. 
    The fact that we identify that our problem is NP-Hard suggests that a complete characterization of the optimal policy is not possible, not even through the MAB framework. 
    
\textit{Sequential search and applications.}
    The stylized sequential search process introduced by \cite{weitzman1979optimal} has been widely used in economics, marketing, and operations research.
    This includes empirical work~\citep{de2012testing, ursu2018power}, behavioral research~\citep{gabaix2006costly}, and economic models that use the Pandora’s box as a discrete-choice framework~\citep{miller1984job, robert1993informative, choi2018consumer, derakhshan2018product, chu2020position, immorlica2020information}.
    Our work offers a richer modeling structure to represent decision-making processes where alternatives can be inspected in stages with varying costs, although our current contribution remains theoretical.
    
    We note in passing about the existence of a literature on sequential search problems modeled using a Bayesian framework where there is a single box that can be sampled repeatedly for a fee and the decision maker tries to decide when to stop sampling with the goal of maximizing the expected value of the highest observed sample minus the sampling costs \cite[see, e.g., the recent work of][and the references therein]{baucells2023search}. Although the idea of sequential inspection is similar to our work, the key characteristics of our model, a tradeoff between cheap and costly inspections across multiple alternatives, are not captured by this literature.




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




