Imagine you are a doctor diagnosing a patient, a robot mapping an unknown environment, or an active learning algorithm selecting images to label for a deep neural network. In each case, you face a sequential decision-making problem under uncertainty. You cannot simply select a fixed batch of actions at the start; the most informative next step depends entirely on the outcomes of your previous observations.
To find the absolute optimal sequence of actions, you would theoretically need to construct a massive decision tree that explores every possible action and every subsequent observation outcome. Because this tree grows exponentially, finding the exact optimal policy is computationally intractable.
Faced with this complexity, practitioners often resort to a greedy policy: simply select the single action that looks best right now. While greedy strategies can fail spectacularly on arbitrary sequential problems by falling into short-sighted traps, a powerful mathematical framework known as adaptive submodularity guarantees that a simple greedy policy will perform near-optimally.
The Intuition of Diminishing Returns
To understand why a greedy policy can succeed sequentially, we must first look at the static concept of submodularity, which formalizes the law of diminishing returns. In a static setting, a set function is submodular if adding an item to a small set provides a larger marginal benefit than adding that same item to a larger, more comprehensive set.
In sequential decision-making, however, we do not just accumulate items; we accumulate a history of observations (actions paired with their observed outcomes). As formalized by Krause et al. in their foundational paper, Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization, an objective function satisfies adaptive submodularity if the expected marginal gain of an action decreases as the history of observations grows.
Crucially, the authors demonstrate that this diminishing returns property must hold in expectation over the posterior distribution of outcomes given the current history, rather than just in individual, isolated states. When this condition is met, information gathered early on can only reduce or maintain—but never increase—the expected utility of future actions. This prevents the greedy algorithm from making choices that seem mediocre now but suddenly become hyper-valuable later, ensuring that short-sighted choices align robustly with global optimization goals.
Why the Greedy Policy Works
When an objective function is both adaptively submodular and monotonically increasing (meaning that making more observations never hurts), the theoretical guarantees are remarkably strong. Krause et al. proved that a greedy policy—which iteratively selects the action maximizing the immediate expected utility gain—is guaranteed to achieve at least a $(1 - 1/e) \approx 63.2\%$ approximation of the optimal sequential policy's value.
As highlighted by the authors in the context of environmental planning (Sequential Decision Making in Computational Sustainability via Adaptive Submodularity), this guarantee bypasses the exponential computational cost of traditional sequential planning methods. It ensures that simple, locally optimal choices lead to near-optimal global outcomes in partially observable environments.
Crafting Submodular Surrogates
A major challenge in real-world applications is that many natural objectives, such as Shannon entropy or the direct Value of Information (VoI), do not satisfy adaptive submodularity. As noted by Fern et al. in Adaptive Submodularity with Varying Query Sets: An Application to Active Multi-label Learning, maximum entropy heuristics can fail to be submodular, causing greedy selection to get stuck in myopic dead ends.
To circumvent this, researchers construct clever submodular surrogates—alternative objective functions that mimic the true goal but are mathematically guaranteed to be adaptively submodular:
- Equivalence Class Edge Cutting ($EC^2$): Introduced by Krause et al. in Near-Optimal Bayesian Active Learning with Noisy Observations, this framework reframes active learning under noise as cutting edges between hypotheses in an equivalence graph, providing the first near-optimal guarantees for noisy observations.
- Equivalence Class Edge Discounting (ECED): To handle scenarios where observations are both noisy and highly correlated, Hassani et al. developed ECED in Near-optimal Bayesian Active Learning with Correlated and Noisy Tests, guaranteeing performance within a logarithmic factor of the optimal policy.
- The Gibbs Error Criterion: Cuong et al. demonstrated in Active Learning for Probabilistic Hypotheses Using the Maximum Gibbs Error Criterion that the Maximum Gibbs Error serves as a robust, provably adaptive submodular objective for active learning with probabilistic hypotheses.
- DIRECT: In Submodular Surrogates for Value of Information, Chen et al. introduced a surrogate that enables non-myopic sequential test selection, bridging the gap between efficient local decision-making and global utility maximization.
Scaling to Batches and Streams
As the field has matured, researchers have extended adaptive submodularity to accommodate modern machine learning workflows, such as batch processing and streaming data.
Batch Mode Active Learning
In deep active learning, evaluating and labeling data points one by one is highly inefficient because it requires retraining the model after every single sample. Instead, systems must select batches of data. Krause et al. proved in Near-optimal Batch Mode Active Learning and Adaptive Submodular Optimization that a greedy selection strategy within batches remains highly competitive with the optimal batch policy, meaning the "price of parallelism" is remarkably low.
However, a naive greedy strategy might select a batch of highly informative but redundant samples (e.g., ten nearly identical images of the same dog). To enforce diversity, Kirsch developed BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning. By greedily maximizing the joint mutual information of an entire batch with the model parameters, BatchBALD leverages submodularity to ensure that the acquired batch is both highly informative and diverse, avoiding combinatorial search.
Data Streams and Real-Time Constraints
When data arrives continuously rather than sitting in a static pool, Kashima et al. showed in Budgeted stream-based active learning via adaptive submodular maximization how to maintain these guarantees. By introducing "policy-adaptive submodularity," the authors proved that sequential decision-making under a fixed budget over a data stream can reliably recover a significant portion of the utility available in static data pools.
Broadening the Boundaries
Recent work has focused on relaxing the strict mathematical assumptions of adaptive submodularity to make it applicable to an even wider array of problems.
The Adaptive Submodularity Ratio
Many real-world problems violate strict adaptive submodularity, yet greedy algorithms still perform exceptionally well on them in practice. To explain this gap between theory and practice, Fujii et al. introduced the adaptive submodularity ratio in Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio. This ratio quantifies exactly how close a function is to being submodular, providing weaker but still rigorous performance bounds for complex tasks like feature selection and influence maximization.
Worst-Case Robustness
Traditional adaptive submodularity optimizes for average-case expected utility. However, in safety-critical domains, average performance is not enough. Tang addressed this in Robust Adaptive Submodular Maximization by defining worst-case submodular functions. This framework allows an adaptive greedy policy to select items that maximize marginal utility in the worst possible scenario, ensuring a strict lower bound on performance regardless of how the environment responds.
Diverse Applications in AI
The mathematical elegance of adaptive submodularity has made it a core tool across a wide range of research areas:
- Sensing Systems: In radar engineering, Esmaeilbeig et al. applied submodular mutual information maximization to efficiently solve the computationally intractable problem of placing Intelligent Reflecting Surfaces (Submodular Optimization for Placement of Intelligent Reflecting Surfaces in Sensing Systems).
- Safety Verification: Zhang et al. framed the problem of finding safe paths in Markov Decision Processes as an adaptive submodular set-cover problem, allowing autonomous agents to minimize human cognitive load when querying for safety constraints (Querying to Find a Safe Policy under Uncertain Safety Constraints in Markov Decision Processes).
- Robotics: In Adaptive Information Gathering via Imitation Learning, Choudhury et al. bypassed heavy on-board probabilistic reasoning by training robots to imitate a "clairvoyant oracle." Because the underlying information-gathering task was adaptively submodular, the learned policy maintained strong near-optimality guarantees.
- Hypothesis Testing: Gan et al. leveraged submodular ranking in Greedy Approximation Algorithms for Active Sequential Hypothesis Testing to develop algorithms whose complexity scales independently of the action space, making them viable for massive real-world problems like genomics-based cancer detection.
By formalizing the intuitive concept of diminishing returns for sequential observations, adaptive submodularity provides the theoretical bedrock that justifies using simple, fast, greedy choices to solve some of the most complex, uncertain problems in artificial intelligence.
Key Foundational Work
Near-Optimal Bayesian Active Learning with Noisy Observations (2010) — contributed 2 concept elements to this direction.
Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization (2010) — contributed 2 concept elements to this direction.
Optimal Order of Decoding for Max-Min Fairness in K-User Memoryless Interference Channels (2007) — contributed 1 concept elements to this direction.