Nearly Minimax Optimal Submodular Maximization with Bandit Feedback

Lalit Jain, Kevin Jamieson, Artin Tajdini

TL;DR

This paper tackles the challenge of learning optimal subsets of items to maximize a "submodular" function (where adding items yields diminishing returns) under noisy, sequential feedback (bandit feedback). They establish a new theoretical lower bound on how well any algorithm can perform and propose a novel algorithm, SUB-UCB, that achieves near-optimal performance, bridging the gap between existing theoretical limits.

What Problem Does This Paper Address?

Imagine you have a set of items (e.g., antibiotics for a patient, content for a webpage) and you want to choose a subset of a fixed size to maximize some outcome (e.g., patient recovery, user engagement). The catch is that the underlying function describing the outcome is unknown, and you only get noisy feedback after trying a subset. Furthermore, the function has a "submodular" property: adding an item to a small set is more beneficial than adding it to a large set (diminishing returns). This is a common scenario in areas like drug discovery, recommender systems, and experimental design.

The core problem is to design an algorithm that efficiently learns the best subset while minimizing "regret" – the difference between the outcome achieved by the algorithm and the best possible outcome if we knew the function perfectly. Existing work has achieved certain regret bounds, but there's a gap between the theoretical best possible performance (lower bound) and what algorithms can actually achieve (upper bound), particularly concerning how the number of items ($n$), the subset size ($k$), and the number of trials ($T$) interact. This paper aims to close this gap by providing tighter theoretical bounds and a matching algorithm.

Methods

The authors introduce a novel algorithm called SUB-UCB (Submodular Upper Confidence Bound). It's inspired by the "Explore-Then-Commit" (ETC) strategy, which is common in bandit problems. The key idea is to first "explore" by greedily building up a subset, adding items one by one using a UCB-like approach to balance exploration and exploitation. This initial greedy phase is designed to be robust to noise and to find a "near-optimal" prefix of the final subset.

After this initial phase, the algorithm switches to a more standard UCB approach, treating the partially built subset as a "base" and exploring different ways to complete it to the target size $k$. This hybrid approach allows SUB-UCB to interpolate between different regret regimes, achieving better performance across various problem scales ($n$, $k$, $T$) than previous methods.

The theoretical contribution involves deriving a new minimax lower bound on the regret. This bound establishes the fundamental limits of what any algorithm can achieve for this problem. The authors achieve this by constructing a "hard instance" – a specific type of submodular function and noise distribution – that is difficult for any algorithm to learn from.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and proposes an algorithm that is evaluated on synthetic "hard instances" designed to test the theoretical bounds.

Key Insights and Ideas

  • The Trade-off is Key: The paper highlights that the optimal regret depends on a complex interplay between the number of items ($n$), the subset size ($k$), and the number of trials ($T$). Previous algorithms often struggled to balance the benefits of exploring many small subsets versus a few large ones.
  • Hybrid Strategy is Optimal: The success of SUB-UCB demonstrates that a hybrid approach, combining a robust greedy exploration phase with a standard UCB phase for larger subsets, is crucial for achieving near-optimal regret.
  • "Robust Greedy Regret" is the Right Metric: The authors emphasize that a specific notion of regret, called "robust greedy regret" ($R_{gr}$), is more appropriate for this problem than simpler notions. This metric accounts for the fact that even if an algorithm finds a set that's close to the optimal, it might still incur regret if it doesn't perfectly match the noiseless greedy solution.
  • Closing the Theoretical Gap: The paper provides the first tight minimax lower bound for this problem, effectively closing the gap between theoretical limits and algorithmic performance.

Key Results

  • New Minimax Lower Bound: The paper establishes a new lower bound on the robust greedy regret of $\tilde{\Omega}(\min_{0 \le L \le k} (L^{1/3}n^{1/3}T^{2/3} + \sqrt{L}T))$. This bound shows that for small $T$, the regret is dominated by the $T^{2/3}$ term (common in bandit problems with structure), while for large $T$, it's dominated by the $\sqrt{T}$ term (typical for standard multi-armed bandits).
  • Near-Optimal Algorithm (SUB-UCB): The proposed SUB-UCB algorithm achieves a regret of $\tilde{O}(\min_{0 \le L \le k} (L n^{1/3}T^{2/3} + \sqrt{L}T))$, which matches the derived lower bound up to logarithmic factors.
  • Improved Bound for Restricted Algorithms: For a slightly restricted class of algorithms, a stronger lower bound of $\tilde{\Omega}(\min_{0 \le L \le k} (L n^{1/3}T^{2/3} + \sqrt{L}T))$ is proven.

Limitations and Future Work

  • Generalization to Other Constraints: The authors note that their work focuses on cardinality constraints. Extending these results to other combinatorial constraints (like matroid constraints) or to non-monotonic submodular functions remains an open challenge.
  • DR-Submodularity and Continuous Settings: Future work could explore similar minimax optimal bounds for DR-submodular functions or for continuous settings, which also have known approximation guarantees.
  • Practical Parameter Tuning: While the paper provides theoretical guarantees, the optimal choice of parameters (like the greedy stop level $l$ in SUB-UCB) might still require some tuning in practice, although the paper suggests $l = k - i^*$ as a good heuristic.

Summary updated

BibTeX
@inproceedings{jain2024nearly,
  author = {Lalit Jain and Kevin Jamieson and Artin Tajdini},
  title = {{Nearly Minimax Optimal Submodular Maximization with Bandit Feedback}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=Vn0FWRImra},
}
Figure