Bounded Adaptivity Gaps in Stochastic Optimization

24 concepts16 papers1 proposal

Imagine navigating a complex sequence of choices under uncertainty—such as interviewing job candidates, opening mystery boxes with hidden rewards, or routing a vehicle through cities with unpredictable traffic. Intuitively, the best approach is an adaptive policy: a dynamic strategy that reacts to real-time feedback, adjusting each subsequent decision based on what has been observed so far.

However, computing an optimal adaptive policy is often a logistical and mathematical nightmare. It requires mapping out an exponential decision tree that quickly becomes computationally intractable when constrained by deadlines, budget limits, or complex dependencies.

This challenge drives a powerful realization across stochastic optimization: non-adaptive strategies—which commit to a fixed sequence or threshold upfront—can perform remarkably close to the best possible adaptive policies. The worst-case ratio between the performance of an optimal adaptive policy and a non-adaptive policy is known as the adaptivity gap. A rich body of research demonstrates that this gap is frequently bounded by a small constant, meaning that simple, pre-planned execution is often sufficient to achieve near-optimal results.


The Core Mechanism: Path Sampling and Virtual Simulation

To understand why a static sequence can approximate a complex, reactive decision tree, we must look at how non-adaptive policies are constructed from adaptive ones.

Consider an optimal adaptive policy as a massive decision tree where every branch represents a different realization of uncertainty. As shown by Anupam Gupta 0001 et al. in Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions, we can derive a highly effective non-adaptive strategy by sampling a single path from this optimal decision tree according to the underlying probability distribution of the item states. Because the adaptive tree is already optimized to maximize expected utility, a single representative path captures a significant, constant fraction of the tree's total value. If a deterministic oracle for the problem is available, these near-optimal fixed sequences can even be computed in polynomial time, bypassing the need for real-time calculation.

Adaptive Decision Tree (Exponential Branches)
       [ Choice A ]
       /          \
   (Success)     (Failure)
   /      \       /      \
[Choice B] ... [Choice C] ...
     \             /
      \           /
   Selected Static Path: [ Choice A -> Choice C -> ... ]

A similar intuition underpins the simulation-based proof technique introduced by Shaojie Tang et al. in Price of Dependence: Stochastic Submodular Maximization with Dependent Items. By virtually executing an optimal adaptive policy across all possible item states, the authors establish a formal mathematical bridge between sequential decision-making and fixed-set selection. This allows them to prove tight adaptivity gaps even when the standard assumption of statistical independence between items is relaxed.


Why Static Sequences Work: Concentration of Measure

Another reason non-adaptive strategies succeed is the phenomenon of statistical concentration. In routing and covering problems, such as the Stochastic $k$-TSP (where a vehicle seeks the shortest tour to collect a target reward $k$ from uncertain locations), real-time feedback might seem crucial. However, Jian Li et al. demonstrate in Algorithms and Adaptivity Gaps for Stochastic k-TSP that when cumulative rewards concentrate predictably around their means, the benefit of real-time adaptation vanishes. A single, robust fixed tour can be constructed to remain highly efficient across the most likely realizations of uncertainty, yielding a constant adaptivity gap.

Even when uncertainty is high and rewards vary widely, non-adaptive strategies can handle the variance by planning for multiple scenarios simultaneously. As explored by Alina Ene et al. in Approximation Algorithms for Stochastic k-TSP, a non-adaptive algorithm can simulate adaptivity by evaluating a sequence against multiple potential remaining reward targets. While this introduces a small logarithmic overhead ($\mathcal{O}(\log^2 k)$), it proves that a static plan can still gracefully handle highly volatile environments.


Application: Sequential Search and Pandora's Box

The power of non-adaptive approximation is vividly illustrated in sequential search frameworks derived from the classic "Pandora's Box" problem, where an agent pays an inspection cost to reveal a hidden reward. While classic variations rely on dynamic index rules, modern constraints like deadlines or precedence graphs make fully adaptive search computationally intractable.

In these constrained environments, pre-commitment strategies offer an elegant escape:

  • Order Constraints: When search options are restricted by directed acyclic graphs, Shant Boodaghians et al. prove in Pandora's Box Problem with Order Constraints that a fixed, non-adaptive selection of exploration targets guarantees at least half the performance of the best possible adaptive strategy.
  • Optional Inspections: In scenarios where an agent can blindly accept a prize without paying to inspect it, Hedyeh Beyhaghi et al. show in Pandora's Problem with Nonobligatory Inspection that a simple "committing policy" partitions options into an inspection sequence and a blind-selection set upfront. This non-adaptive partition guarantees at least 63.2% of the optimal adaptive value.
  • Deadlines and Time Slots: When items are only available for a limited time, Ben Berger et al. leverage the bounded gap between adaptive and non-adaptive policies in Pandora's Problem with Deadlines to design a constant-factor approximation algorithm that completely avoids real-time adjustments.

As surveyed by Hedyeh Beyhaghi et al. in Recent Developments in Pandora's Box Problem: Variants and Applications, a fixed inspection order remains remarkably robust—and often strictly optimal—across a wide range of complex search variants, including those featuring submodular cost structures.


Application: Resource Budgets and Selection Pipelines

The utility of static ordering extends directly to resource-constrained problems like knapsack packing, matching, and hiring pipelines.

Unknown Capacities

In many real-world settings, you must commit to items without knowing your total budget or capacity limit until you hit it. Max Klimm et al. study this in Packing a Knapsack of Unknown Capacity and prove that a universal, fixed-order packing strategy is fundamentally as powerful as any adaptive strategy in the worst case. Real-time adjustments based on whether previous items fit cannot improve the worst-case guarantee. Similarly, Hanna Sumita et al. demonstrate in Submodular maximization with uncertain knapsack capacity that pre-computed, fixed sequences perform within a constant factor of adaptive policies when maximizing submodular objectives under capacity uncertainty.

Hiring and Matching Pipelines

When recruiting candidates or matching resources under uncertainty, choices carry a commitment cost. Manish Purohit et al. demonstrate in Hiring Under Uncertainty that a fixed-order selection strategy based on candidate value achieves a constant-factor approximation of the optimal adaptive decision tree.

This principle is reinforced by Boris Epstein et al. in Order Selection Problems in Hiring Pipelines, where setting a fixed sequence of interviews and offers upfront achieves at least $1 - 1/e$ ($\approx 63.2\%$) of adaptive performance.

To simplify operations further, Nick Arnosti et al. show in Tight Guarantees for Static Threshold Policies in the Prophet Secretary Problem that a simple policy applying a single fixed threshold throughout the entire process provides near-optimal guarantees, proving that decision-makers do not need to dynamically lower their standards as time runs out.

Computational Efficiency

Ultimately, swapping adaptive policies for static sequences yields massive computational savings. As demonstrated by Anupam Gupta et al. in both When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings and Non-Adaptive Stochastic Score Classification and Explainable Halfspace Evaluation, fixed testing and probing sequences achieve robust constant-factor approximations while executing orders of magnitude faster than their fully adaptive counterparts. By establishing that the adaptivity gap is tightly bounded, this line of research provides a rigorous justification for using simple, predictable, and explainable static strategies across complex stochastic environments.

Key Foundational Work

When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings (2010) — contributed 1 concept elements to this direction.
Packing a Knapsack of Unknown Capacity (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_adaptive_approximation_58ae0fdf,
  title = {non-adaptive approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-adaptive-approximation/rdr_58ae0fdfe0334110aebff74326660e9b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_adaptive_approximation_58ae0fdf_v1,
  title = {non-adaptive approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-adaptive-approximation/rdr_58ae0fdfe0334110aebff74326660e9b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake