Pandora's Knapsack via Simple Policies
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Pandora's Knapsack via Simple Policies".
Jane: Here's the gist of the paper. Pandora’s Knapsack is introduced as a hybrid problem combining elements of stochastic knapsack and Pandora’s box, where items have sizes drawn from known distributions and incur opening costs before their sizes are revealed.
Tom: The study investigates the efficacy of simple decision-making policies in approximating this problem across two dimensions: knowledge of size distributions and adaptivity.
Jane: The introduction of opening costs fundamentally alters the algorithmic landscape of stochastic knapsack problems, necessitating more complex policies along both complexity axes to achieve approximate optimality.
Tom: However, with full distributional information and a degree of adaptivity that permits adaptive skipping of items, a constant approximation factor can be recovered.
Paper summary: Tom: So we're looking at this paper today called "Pandora's Knapsack via Simple Policies." Basically, they introduce this new problem that mixes two things: the classic stochastic knapsack problem and Pandora's box.
Jane: That sounds complicated. Can you break down what makes it a hybrid? What’s the main idea they are trying to solve here?
Tom: Well, as in stochastic knapsack, you have items with known size distributions, and if an item fits in your knapsack, you get its value. But with Pandora's box added, every time you consider an item, you first have to pay a cost just to open the box before you even know the item's size or whether it fits.
Lu: The core challenge they identify is that this opening cost completely changes the whole algorithmic landscape of stochastic knapsack problems <ref:2509.05956#pg1>. It means you need much more complex policies, along both complexity axes: how much information you have about the sizes, and how adaptive your decision-making is.
Meng: From my side at scale, I'm worried about those costs upfront. If you pay to open a box before knowing if it’s worth taking, that asymmetry between cost and reward becomes really punishing when things are uncertain <ref:2509.05956#pg3>.
Jane: So the paper claims they found a way around this complexity. What's the big takeaway they offer about solving this hybrid problem?
Tom: They show that even with full knowledge of the size distributions and a degree of adaptivity—specifically, allowing adaptive skipping of items—you can recover a constant approximation factor for optimal performance <ref:2509.05956#pg1>.
Lu: That constant factor is achieved by using simple decision-making policies, which they characterize through something they call Return-on-Investment or ROI. This ROI smoothly describes how effective these simple policies are across a whole hierarchy of increasingly adaptive strategies <ref:2509.05956#pg1>.
Meng: I need to know what this means for deployment at scale. If a policy is only good if the ROI is high, that's not very robust when you're running millions of jobs <ref:2509.05956#pg2>.
Tom: The analysis shows that ROI exactly captures the adaptivity gap in the classic Pandora’s Box problem and that simple policies are approximately optimal as long as their ROI is high enough <ref:2509.05956#pg1>. They looked at several policy types: Batch, NonAdaptive, StoppingAdaptive, SkippingAdaptive, and FullyAdaptive policies.
Paper summary: Jane: That's a lot of policy types to juggle. What happens when you look at the lower bounds they establish for these simpler methods?
Lu: They show that any policy with limited knowledge about the size distributions is at least an alpha factor worse than the optimal fully adaptive policy when you have all that information <ref:2509.05956#pg2>. And non-adaptive policies are at least alpha away from the optimal fully adaptive policy when those opening costs are present <ref:2509.05956#pg1>.
Meng: If it's at least alpha away, that means for a large enough problem, I'm going to be stuck with a significant performance hit if I don't use the most complex adaptive strategy <ref:2509.05956#pg2>.
Tom: But they find something promising. They demonstrate that skipping-adaptive policies are actually sufficient to get a constant factor approximation of the optimal fully-adaptive policy <ref:2509.05956#pg1>. This is a big win for practicality because it suggests we don't need the most complex adaptive policy to get a good result.
Jane: I see how that helps someone who just wants a reliable solution without needing perfect, fully adaptive intelligence. But what about when we move from known distributions to actual uncertain values?
Lu: They extend this idea by replacing those fixed distribution values with their expected counterparts, turning it into a stochastic value problem <ref:2509.05956#pg2>. In that context, neither knowing only the first few moments of the size distributions nor fixing the job order while allowing adaptive stopping is enough for a constant approximation in these initial results <ref:2509.05956#pg1>.
Meng: So even when you have some statistical information, you still need some level of adaptation just to stay within a constant factor of optimal performance <ref:2509.05956#pg2>. That sounds like it would be tough to deploy reliably.
Tom: They quantify that relationship by looking at the ratio between two different policy approaches: ADAPT over BATCH, and this ratio is Theta of alpha tilde <ref:2509.05956#pg2>. Theorem six point two shows that for every Pandora’s box instance, the ratio of these two is less than or equal to two times one plus alpha tilde <ref:2509.05956#pg2>.
Jane: So if we have a large alpha tilde, this ratio is still bounded by something manageable, like three times one plus that number. How does that translate into real-world performance gains?
Paper summary: Lu: The matching lower bound they proved is Theta of alpha tilde, which means as the uncertainty parameter grows, the gap between these two methods also grows in a controlled way <ref:2509.05956#pg2>. This shows that the relationship between ADAPT over BATCH and alpha tilde is proportional to that parameter <ref:2509.05956#pg1>.
Meng: I'm trying to figure out what this means for my production system. If I use a batch policy, how much worse am I compared to using an adaptive stopping policy?
Tom: Section six point two shows that the gap between non-adaptive policies and policies that adaptively decide when to stop depends on alpha tilde, and that dependence is tight, meaning you can find instances where the gap is alpha tilde <ref:2509.05956#pg1>.
Jane: So it's not just a fixed difference; there are specific tricky instances where the performance drop between being non-adaptive and being adaptive stopping is proportional to that uncertainty measure. That's a nuanced point.
Lu: They also looked at why stopping-adaptive policies aren't enough on their own by showing their gap from the optimal adaptive policy can be alpha one over three <ref:2509.05956#pg1>. So, stopping adaptive isn't quite optimal for this specific problem <ref:2509.05956#pg1>.
Tom: But they do give us a way forward by providing an efficient algorithm for computing a skipping-adaptive policy that achieves that constant factor approximation of the optimal fully-adaptive policy <ref:2509.05956#pg1>. That’s the practical tool they give us.
Meng: An algorithm to compute it is better than just hoping a policy works well, but what's the computational cost of running that skipping-adaptive policy? I need to know if it breaks at scale <ref:2509.05956#pg2>.
Jane: The focus here seems to be on showing that this skipping-adaptive approach gives us a constant factor approximation regardless of the distribution complexity, provided we have enough adaptivity in our decision-making <ref:2509.05956#pg1>.
Lu: This work confirms that simple policies can be nearly optimal if the Return-on-Investment parameter is large enough, which ties everything back to how much information you have versus how much adaptation you can afford <ref:2509.05956#pg1>.
Tom: So, in a nutshell, "Pandora's Knapsack via Simple Policies" shows that by focusing on the right kind of adaptivity—specifically skipping items when costs are involved—we can keep our performance close to optimal without needing the most complex decision-making framework <ref:2509.05956#pg1>.
Jane: It seems like the paper gives us a concrete roadmap for choosing a policy based on how much uncertainty we’re willing to tolerate versus how much computation we can afford <ref:2509.05956#pg1>.
Conclusion: Tom: So, let's talk about "Pandora’s Knapsack via Simple Policies." Who wrote this?
Jane: The authors are exploring how you can use less complex policies to get a good result on a problem that has both uncertainty in item sizes and those upfront opening costs.
Lu: They introduce this framework where you look at different levels of adaptivity, from batch processing all the way up to fully adaptive policies.
Meng: And they show that even with this setup, if you use simple policies like skipping adaptive ones, you can still get a constant factor approximation to the best possible outcome.
Tom: So it's not about needing the most complicated AI strategy for every single job, as long as your policy is set up right.
Jane: Exactly. It suggests that with enough adaptivity in your decision-making process, you don't always need to use the most powerful method available to keep things close to optimal.
Lu: They tie this effectiveness directly to something they call Return on Investment, which tells you how good a simple policy is across a whole range of adaptivity levels.
Meng: And that ROI parameter acts like a gate; if the ROI is high enough, your simpler policy works well for you in practice.
Tom: It seems like the paper is really focusing on giving practitioners a practical tool to choose between complexity and accuracy based on those numbers.
Jane: Right. It’s about finding that sweet spot where you get solid performance without needing an infinitely complex AI model running everything constantly.
Lu: The authors also look at how this holds up when the item sizes aren't perfectly known, moving into stochastic values instead of fixed numbers.
Meng: That means it’s not just a theoretical exercise with clean data; they tested it against real-world uncertainty where you only have some statistical estimates for those sizes.
Tom: And they quantify the gap between different policy types, showing that certain policies are significantly worse than others when you have to pay those opening costs.
Jane: It’s a roadmap for engineers trying to balance the cost of making decisions against how accurate they need to be in their final selection.
Lu: This whole paper really boils down to the idea that simple, well-tuned policies can achieve near-optimal performance across these tricky mixed problems.
Tel Aviv University · Hebrew University · Bar-Ilan University
cs.GT
Submitted: 2025-09-07
Updated: 2026-11-10
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 89/100
The gist: Pandora’s Knapsack is introduced as a hybrid problem combining elements of stochastic knapsack and Pandora’s box…
Key concepts
- Return-on-Investment (ROI)
- This economic measure quantifies the effectiveness of a simple decision policy. It smoothly describes how well a policy performs as its adaptivity level increases, indicating the trade-off between complexity and approximation quality in solving the problem.
- Policy Hierarchy
- The paper compares different decision strategies, such as Batch, NonAdaptive, StoppingAdaptive, SkippingAdaptive, and FullyAdaptive. This hierarchy helps map out how adding more knowledge or adaptivity improves a policy's ability to approximate the optimal solution for Pandora's Knapsack.
- Adaptivity Gap
- This refers to the difference in performance between a simple policy and the optimal fully adaptive policy. The analysis shows that certain policies, like skipping-adaptive ones, can bridge this gap to achieve a constant approximation factor, meaning they get close enough to the best possible solution.
- Stochastic Values
- This refers to replacing fixed item sizes with their expected values when dealing with stochastic (random) distributions. The study investigates how performance changes when the decision-making relies only on these expected values instead of knowing the true underlying size distributions.
Terminology
Summary
Pandora’s Knapsack is introduced as a hybrid problem combining elements of stochastic knapsack and Pandora’s box, where items have sizes drawn from known distributions and incur opening costs before their sizes are revealed. p. 0 As in stochastic knapsack, items have
sizes drawn from known distributions, and items that fit within a knapsack contribute to the
total value. As in Pandora, every item i comes in a box that costs ci to open. What distinguishes
our problem is that the size is revealed only after opening the box and paying the cost. We study the power of simple decision-making policies to approximate Pandora’s Knapsack,
along two complexity axes: (i) knowledge of size distributions, and (ii) adaptivity.Where the paper says it
Where the paper says it
The introduction of opening costs fundamentally alters the algorithmic landscape of stochastic knapsack problems, necessitating more complex policies along both complexity axes to achieve approximate optimality. p. 0 We study the power of simple decision-making policies to approximate Pandora’s Knapsack,
along two complexity axes: (i) knowledge of size distributions, and (ii) adaptivity. We show
that adding costs to stochastic knapsack completely changes the algorithmic landscape, and
policies must now be complex along both axes to be approximately-optimal. We show
that adding costs to stochastic knapsack completely changes the algorithmic landscape, and
policies must now be complex along both axes to be approximately-optimal. We complement
these impossibilities by showing that with full distributional information and slightly more
adaptivity—allowing adaptive skipping of items—a constant approximation can be recovered. Our analysis reveals an economic quantity, namely ROI (return-on-investment, defined as
the jobs’ minimum utility over cost), which smoothly characterizes the performance of simple
policies. Across a hierarchy of increasingly adaptive policies, we establish near-tight adaptivity
gaps all governed by ROI.Where the paper says it
Where the paper says it
Where the paper says it
The analysis establishes near-tight adaptivity gaps governed by ROI across this policy hierarchy. p. 0 Our analysis reveals an economic quantity, namely ROI (return-on-investment, defined as
the jobs’ minimum utility over cost), which smoothly characterizes the performance of simple
policies. Across a hierarchy of increasingly adaptive policies, we establish near-tight adaptivity
gaps all governed by ROI. To demonstrate the importance of the ROI parameter in characterizing
simple policies, we revisit Pandora’s Box, and show that return-on-investment exactly captures
the adaptivity gap in this classic problem as well. As a corollary, we get that simple policies are
approximately-optimal provided the ROI is sufficiently large. We interpret these results as saying that ROI characterizes the power of limited adaptivity for
Pandora’s Knapsack, and that skipping-adaptivity is the appropriate level of adaptivity for this
problem. more adaptivity
Batch NonAdaptive
StoppingAdaptive
SkippingAdaptive
FullyAdaptive
Thm 4. We prove in Theorem 4. 1 that any
policy, adaptive or not, whose access to each size distribution is limited to finitely many moments
and overflow probabilities, can be an Ω(α)-factor worse than the optimal policy with full distributional information. Weitzman’s optimal policy opens boxes in a fixed order, but stops once the expected
marginal gain from opening the next box is non-positive; in this sense, it is a stopping-adaptive
policy. A non-adaptive policy, by contrast, chooses in advance a set of boxes to open and pays their
costs. However, a slightly richer form of
adaptivity does suffice: We consider skipping-adaptive policies, which follow a fixed order but assign
each job a threshold, and skip that job whenever the remaining time is below the threshold. This
ability to skip unpromising jobs, while limited, is enough to obtain a constant-factor approximation
to the optimal fully-adaptive policy.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The results extend to stochastic values by replacing deterministic values with their expected counterparts. p. 3 The multichoice feature captures settings in which each job can be executed in one of several possible modes,
with corresponding execution costs and size distributions. In our above example, the PI can choose
1Our results extend in a straightforward manner to stochastic values, by letting the expected value play the role
of the deterministic one. This changes the objective from
reward-only to mixed-sign, and makes it substantially harder for simple policies to approximate
the optimal adaptive policy. In our first set of results, we show that neither knowing only the first
k moments of the size distributions, nor fixing the order of jobs in advance while allowing adaptive
stopping, is sufficient for a constant approximation. This creates a fundamental difference and indeed in
their model the adaptivity gap is constant. We further discuss the relationship to classic Pandora’s
Box in Appendix A. Choosing such a probability ensures that, on the one hand, the value
obtained is not too small compared to optimal policy’s obtained value, and on the other hand, the
additional cost of opening all boxes simultaneously is not too-high. For the matching lower bound,
we consider an instance with identical boxes with Bernoulli value distribution that gives high value
with small probability. Our upper bounds are based on LP relaxations that upper-bound the utility of
fully-adaptive policies, and guide us in choosing which items the simple policy should pick in order
to obtain high expected utility. For the O(α)-approximation, we adapt the stochastic-knapsack
LP [31] to handle costs and multiple choices per item.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The analysis also characterizes the gap between non-adaptive policies and policies that adaptively decide when to stop. p. 3 For nonadaptive policies and policies with limited distributional information, we prove matching lower and
upper bounds, up to constant factors, which are characterized exactly by the ROI. We also revisit
the classic Pandora’s Box problem and show that ROI characterizes the adaptivity gap between
non-adaptive policies and policies that adaptively decide when to stop. 2 Reduction . 33
8 Conclusion 34
A Detailed Related Work: Pandora’s Box, Fixed Subsets, and ROI 39
B Appendix for Section 5. This
dependence is tight up to constants: our O(α)-approximate batch policy uses only first-moment
and overflow-probability information (Theorem 5. Adaptivity Gap Characterized by ROI. We then ask which limited forms of
adaptivity suffice to remove the ROI dependence. We first show that stopping-adaptive policies,
which are optimal for the Pandora’s box problem, are not enough in our context: even though
they may halt when continuing has negative expected utility, their gap from the optimal adaptive
policy can be Ω(α
1/3
) (Theorem 4.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The paper further explores the necessity of adaptivity by examining which limited forms suffice to eliminate ROI dependence. p. 5 Constant Approximation with Limited Adaptivity. We then ask which limited forms of
adaptivity suffice to remove the ROI dependence. We then ask which limited forms of
adaptivity suffice to remove the ROI dependence. We first show that stopping-adaptive policies,
which are optimal for the Pandora’s box problem, are not enough in our context: even though
they may halt when continuing has negative expected utility, their gap from the optimal adaptive
policy can be Ω(α
1/3
) (Theorem 4. We first show that stopping-adaptive policies,
which are optimal for the Pandora’s box problem, are not enough in our context: even though
they may halt when continuing has negative expected utility, their gap from the optimal adaptive
policy can be Ω(α
1/3
) (Theorem 4. Finally, we give an efficient algorithm that computes a
skipping-adaptive policy with a constant-factor approximation to the optimal fully-adaptive policy
(Theorem 5.Where the paper says it
Where the paper says it
Where the paper says it
The relationship between ADAPT(I)/BATCH(I) and alpha tilde is also shown to be theta(alpha tilde). p. 7 As we have shown that our policy cannot use a fixed execution order, and limited distributional
knowledge, our policy uses richer distributional information and allows deviating from the fixed
execution order. We adapt the global time-indexed LP framework [3, 33, 42], and design an algorithm that extracts a constant fraction of its value. To demonstrate the importance of the ROI parameter in characterizing
simple policies, we revisit Pandora’s Box, and show that return-on-investment exactly captures
the adaptivity gap in this classic problem as well. As a corollary, we get that simple policies are
approximately-optimal provided the ROI is sufficiently large.Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Better policy design for Pandora’s Knapsack can be achieved by using skipping-adaptive policies to obtain a constant factor approximation to optimal fully-adaptive policies, as shown in Theorem 5.1. This allows an AI system to achieve near-optimal utility with limited adaptivity without needing full information about item sizes or the ability to choose the next job based on the full history.
-
Robust performance in contract design can be guaranteed by reducing the problem to Multi-choice Pandora’s Knapsack, allowing agents to choose effort levels and principal costs to be modeled as expected transfers, as established in Proposition 7.1 and Section 7.2. This enables AI systems to find policies that approximate optimal agent incentives by solving the MPK problem.
-
The system can leverage Return-on-Investment (ROI) as a guiding parameter for policy selection; specifically, ROI characterizes the adaptivity gap between simple policies and optimal adaptive ones, allowing the AI to make decisions based on whether an item's upfront cost is justified by its expected utility.
-
For contract design problems with costs, the system can use an O(alpha) approximate batch policy to achieve near-optimal results for a given parameter alpha, as demonstrated in Theorem 5.4 and Section 7.2. This provides a polynomial-time algorithm that selects a subset of jobs to attempt based on density criteria derived from ROI.
-
The system can be designed to recover constant approximation guarantees for the classic Pandora’s Box model by employing randomized non-adaptive policies, which are approximately optimal relative to the optimal adaptive policy with respect to the Tail Inverse ROI parameter, as shown in Theorem 6.2 and Section 6.1.
Abstract
We introduce Pandora's Knapsack: a hybrid of the classic stochastic knapsack [Dean, Goemans, and Vondr'ak, 2008] and Pandora's box [Weitzman, 1979]. As in stochastic knapsack, items have sizes drawn from known distributions, and items that fit within a knapsack contribute to the total value. As in Pandora, every item i comes in a box that costs c i to open. What distinguishes our problem is that the size is revealed only after opening the box and paying the cost. A motivating application from contract design is knapsack contracts, where a principal sequentially delegates jobs with stochastic processing times to agents before a deadline, and must pay each agent to incentivize effort, even if the job ends up not completing in time. We study the power of simple decision-making policies to approximate Pandora's Knapsack, along two complexity axes: (i) knowledge of size distributions, and (ii) adaptivity. We show that, compared to the classic stochastic knapsack and Pandora's box, policies in our model must be significantly more complex along both axes to be approximately optimal. Conversely, we show that with full distributional information and by allowing adaptive skipping of items, a constant approximation can be recovered. Our analysis reveals an economic quantity, namely ROI (return-on-investment, defined as the jobs' minimum utility over cost), which smoothly characterizes the performance of simple policies. Across a hierarchy of increasingly adaptive policies, we establish tight adaptivity gaps all governed by ROI. To demonstrate the importance of the ROI parameter in characterizing simple policies, we revisit Pandora's box, and show that return-on-investment exactly captures the adaptivity gap in this classic problem as well.
Sources
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments