# Adaptive Sequence Submodularity

arXiv: https://arxiv.org/abs/1902.05981 · HTML: https://mlsanity.com/paper/1902.05981/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2019.

## Built on by (most cited first, 8 of 8)

- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [The Power of Subsampling in Submodular Maximization](https://mlsanity.com/paper/2104.02772/) (2021)
- [Tokenized Bandit for LLM Decoding and Alignment](https://mlsanity.com/paper/2506.07276/) (2025)
- [Multi-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences](https://mlsanity.com/paper/2104.09884/) (2021)
- [Sequence Adaptation via Reinforcement Learning in Recommender Systems](https://mlsanity.com/paper/2108.01442/) (2021)
- [Deep Submodular Peripteral Networks](https://mlsanity.com/paper/2403.08199/) (2024)
- [Robust Sequence Networked Submodular Maximization](https://mlsanity.com/paper/2212.13725/) (2022)
- [Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies](https://mlsanity.com/paper/2404.01930/) (2024)

## Abstract (arXiv)

In many machine learning applications, one needs to interactively select a sequence of items (e.g., recommending movies based on a user's feedback) or make sequential decisions in a certain order (e.g., guiding an agent through a series of states). Not only do sequences already pose a dauntingly large search space, but we must also take into account past observations, as well as the uncertainty of future outcomes. Without further structure, finding an optimal sequence is notoriously challenging, if not completely intractable. In this paper, we view the problem of adaptive and sequential decision making through the lens of submodularity and propose an adaptive greedy policy with strong theoretical guarantees. Additionally, to demonstrate the practical utility of our results, we run experiments on Amazon product recommendation and Wikipedia link prediction tasks.