Adaptive Submodular Optimization for Sequential Influence

This direction is split into other directions: adaptive influence maximization. Its last version stays readable and citable here.

Version 1 of 158 papers85 conceptsfrozen 2026-10-04

In traditional influence maximization, a decision-maker selects a "seed set" of users to trigger a viral cascade, assuming the network's response is a black box that only reveals itself after all choices are made. This "one-shot" approach is akin to playing a game of chess by deciding every move before the opponent has even touched a piece.

Researchers like Andreas Krause and Daniel Golovin have pioneered a more responsive framework: Adaptive Submodularity. By treating influence as a sequential decision process, we can observe the results of each "move" and adjust our strategy in real-time, significantly increasing efficiency and reducing the cost of information spread.

The Intuition of Diminishing Returns

At the heart of this research is the concept of submodularity, a mathematical formalization of "diminishing returns." In a static setting, adding an element to a small set provides more marginal value than adding it to a large set. For example, the first person you tell a secret to provides a massive boost in "coverage," while the hundredth person likely already heard it from someone else.

In Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization, Daniel Golovin and Andreas Krause extend this to stochastic environments. Here, the state of an element (e.g., whether a user will actually share a post) is unknown until it is selected. An adaptive policy doesn't just pick a set; it picks a function that maps current observations to the next action.

Why the Greedy Strategy Wins

The most striking result in this field is that a simple adaptive greedy policy—selecting the next action that maximizes the expected marginal gain given the current history—is often near-optimal.

Andreas Krause and Daniel Golovin proved in Adaptive Submodular Optimization under Matroid Constraints that for certain complex constraints, this greedy approach is guaranteed to achieve at least a $1/(p+1)$ fraction of the optimal policy's performance. This provides a rigorous justification for "opportunistic" decision-making: if you always take the best step available based on what you currently know, you cannot fall too far behind a "clairvoyant" strategy that knows the future.

Closing the Adaptivity Gap

Why go through the trouble of observing feedback? The "adaptivity gap" represents the potential gain of an adaptive strategy over a static one. In Adaptive Influence Maximization in Dynamic Social Networks, Shaojie Tang and colleagues demonstrated that waiting for a diffusion process to stabilize before picking the next seed can improve influence spread by up to 320%.

The benefit is twofold:

  1. Redundancy Elimination: If a target community is already activated by a previous seed, an adaptive policy avoids wasting resources on redundant influencers in that area (Jing Tang, Keke Huang).
  2. Uncertainty Reduction: Real-time feedback allows the agent to "probe" the network, revealing the actual connectivity of edges rather than relying on estimated probabilities (Takuro Fukunaga).

Real-World Impact: From Conservation to Public Health

This framework isn't just theoretical; it solves high-stakes allocation problems where resources are scarce.

Challenges: Partial and Myopic Feedback

In many networks, we cannot see the whole picture. We might only observe the status of immediate neighbors—a condition known as myopic feedback.

Binghui Peng and Wei Chen explored this in Adaptive Influence Maximization with Myopic Feedback, proving that even with limited visibility, the gap between adaptive and non-adaptive strategies remains bounded. Furthermore, Jing Yuan and Shaojie Tang showed in No Time to Observe: Adaptive Influence Maximization with Partial Feedback that we don't need to wait for a cascade to finish. Observing mid-cascade data allows for "impatient" selection that still captures the majority of adaptive benefits, bridging the gap between speed and intelligence.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_adaptive_submodular_optimization_for_seq_1cc3a8b4,
  title = {Adaptive Submodular Optimization for Sequential Influence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-submodular-optimization-for-sequential-influence/rdr_1cc3a8b4c50a47d9a92c8108f3daf927},
  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_adaptive_submodular_optimization_for_seq_1cc3a8b4_v1,
  title = {Adaptive Submodular Optimization for Sequential Influence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-submodular-optimization-for-sequential-influence/rdr_1cc3a8b4c50a47d9a92c8108f3daf927/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}