# Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 29 references that are in the map.
- First posted on arXiv 2 Apr 2024.

## Builds on (most cited first, 10 of 10)

- [Active Learning: Problem Settings and Recent Developments](https://mlsanity.com/paper/2012.04225/) (2020)
- [Adaptivity in Adaptive Submodularity](https://mlsanity.com/paper/1911.03620/) (2019)
- [Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint](https://mlsanity.com/paper/2007.05014/) (2020)
- [Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time](https://mlsanity.com/paper/2008.05004/) (2020)
- [Adaptive Sequence Submodularity](https://mlsanity.com/paper/1902.05981/) (2019)
- [Adaptive Influence Maximization in Dynamic Social Networks](https://mlsanity.com/paper/1506.06294/) (2015)
- [Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio](https://mlsanity.com/paper/1904.10748/) (2019)
- [Robust Adaptive Submodular Maximization](https://mlsanity.com/paper/2107.11333/) (2021)
- [Streaming Adaptive Submodular Maximization](https://mlsanity.com/paper/2208.08021/) (2022)
- [Submodular Learning and Covering with Response-Dependent Costs](https://mlsanity.com/paper/1602.07120/) (2016)

## Abstract (arXiv)

We study adaptive combinatorial maximization, which is a core challenge in machine learning, with applications in active learning as well as many other domains. We study the Bayesian setting, and consider the objectives of maximization under a cardinality constraint and minimum cost coverage. We provide new comprehensive approximation guarantees that subsume previous results, as well as considerably strengthen them. Our approximation guarantees simultaneously support the maximal gain ratio as well as near-submodular utility functions, and include both maximization under a cardinality constraint and a minimum cost coverage guarantee. In addition, we provided an approximation guarantee for a modified prior, which is crucial for obtaining active learning guarantees that do not depend on the smallest probability in the prior. Moreover, we discover a new parameter of adaptive selection policies, which we term the "maximal gain ratio". We show that this parameter is strictly less restrictive than the greedy approximation parameter that has been used in previous approximation guarantees, and show that it can be used to provide stronger approximation guarantees than previous results. In particular, we show that the maximal gain ratio is never larger than the greedy approximation factor of a policy, and that it can be considerably smaller. This provides a new insight into the properties that make a policy useful for adaptive combinatorial maximization.