In many real-world optimization problems, the parameters—such as the reward of a location, the compatibility of a donor, or the influence of a social contact—are unknown until we interact with them. This uncertainty creates a fundamental architectural choice: do we commit to a fixed plan upfront (non-adaptive), or do we adjust our next move based on the outcomes of previous steps (adaptive)?
The study of the adaptivity gap seeks to quantify the performance ratio between these two approaches. It asks a simple but profound question: how much value do we lose by being rigid?
The Cost of Flexibility
An adaptive strategy can be visualized as a decision tree where every branch represents a possible outcome of a stochastic event. While theoretically powerful, these strategies are often computationally intractable (PSPACE-hard) because the number of possible scenarios grows exponentially. As noted by Danny Segev and Sahil Singla in Efficient Approximation Schemes for Stochastic Probing and Prophet Problems, the overhead of maintaining such a complex policy often outweighs its benefits.
The adaptivity gap is the formal tool used to justify simpler algorithms. If the gap is a small constant, it means a fixed, non-adaptive sequence is nearly as good as the most complex reactive policy. For example, Jian Li and colleagues proved in Algorithms and Adaptivity Gaps for Stochastic k-TSP that for certain routing problems, a fixed tour is a constant-factor approximation of the best adaptive strategy, resolving a major open question.
Bridging the Gap with Limited Adaptivity
When the gap between non-adaptive and fully adaptive strategies is large—sometimes exponentially so—researchers look for a middle ground. In Stochastic Submodular Cover with Limited Adaptivity, Sepehr Assadi and his co-authors show that you don't need to react to every observation. Instead, by using a "batch" approach—making decisions in a few discrete rounds—you can achieve near-optimal performance with significantly less complexity.
This "locally-adaptive" or "semi-adaptive" framework, also explored by Ashwinkumar Badanidiyuru and Yaron Singer in Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions, allows for parallelization and reduced communication costs while still capturing the lion's share of the benefits that come from observing stochastic realizations.
When Information Misleads
Intuitively, more information should lead to better decisions. However, research into the Greedy Adaptivity Gap reveals a counter-intuitive phenomenon: a greedy algorithm that adapts to real-time feedback can sometimes perform worse than one that ignores it.
Binghui Peng and Wei Chen demonstrate in Adaptive Greedy versus Non-Adaptive Greedy for Influence Maximization that because greedy heuristics make locally optimal choices, the "myopic" feedback they receive can lead them down suboptimal paths. This highlights that the value of adaptivity is not just about having data, but about having an algorithm capable of processing that data globally rather than locally.
Universal Robustness
Recent work has pushed toward "black-box" reductions that unify these concepts. Rajan Udwani in Online Submodular Welfare Maximization Meets Post-Allocation Stochasticity and Reusability showed that simple greedy rules can be surprisingly optimal across various stochastic settings. By proving that non-adaptive strategies can match the worst-case guarantees of adaptive ones, this research direction provides a theoretical foundation for using robust, simple algorithms in highly uncertain, dynamic environments.