# Stochastic Multi-round Submodular Optimization with Budget

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

## Key facts

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

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

- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [A Stochastic Probing Problem with Applications](https://mlsanity.com/paper/1302.5913/) (2013)
- [Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions](https://mlsanity.com/paper/1608.00673/) (2016)
- [Controlling Elections through Social Influence](https://mlsanity.com/paper/1711.08615/) (2017)
- [Budgeted Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2202.03704/) (2022)
- [(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing](https://mlsanity.com/paper/1902.01461/) (2019)
- [Time-constrained Adaptive Influence Maximization](https://mlsanity.com/paper/2001.01742/) (2020)
- [Adaptive Influence Maximization with Myopic Feedback](https://mlsanity.com/paper/1905.11663/) (2019)
- [Adaptive Greedy versus Non-adaptive Greedy for Influence Maximization](https://mlsanity.com/paper/1911.08164/) (2019)
- [Election Manipulation on Social Networks: Seeding, Edge Removal, Edge Addition](https://mlsanity.com/paper/1911.06198/) (2019)
- [Sequential Posted Price Mechanisms with Correlated Valuations](https://mlsanity.com/paper/1503.02200/) (2015)
- [On Adaptivity Gaps of Influence Maximization under the Independent Cascade Model with Full Adoption Feedback](https://mlsanity.com/paper/1907.01707/) (2019)
- [Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback](https://mlsanity.com/paper/2006.15374/) (2020)
- [Improved Approximation Factor for Adaptive Influence Maximization via Simple Greedy Strategies](https://mlsanity.com/paper/2007.09065/) (2020)

## Abstract (arXiv)

In this work, we study the Stochastic Budgeted Multi-round Submodular Maximization (SBMSm) problem, where we aim to adaptively maximize the sum, over multiple rounds, of a monotone and submodular objective function defined on subsets of items. The objective function also depends on the realization of stochastic events, and the total number of items we can select over all rounds is bounded by a limited budget. This problem extends, and generalizes to multiple round settings, well-studied problems such as (adaptive) influence maximization and stochastic probing. We show that, if the number of items and stochastic events is somehow bounded, there is a polynomial time dynamic programming algorithm for SBMSm. Then, we provide a simple greedy 1/2(1-1/e-ε)≈ 0.316-approximation algorithm for SBMSm, that first non-adaptively allocates the budget to be spent at each round, and then greedily and adaptively maximizes the objective function by using the budget assigned at each round. Finally, we introduce the em budget-adaptivity gap, by which we measure how much an adaptive policy for SBMSm is better than an optimal partially adaptive one that, as in our greedy algorithm, determines the budget allocation in advance. We show that the budget-adaptivity gap lies between e/(e-1)≈ 1.582 and 2.