Minimax Optimal Submodular Optimization with Bandit Feedback

Artin Tajdini, Lalit Jain, Kevin Jamieson

TL;DR

This paper tackles the challenge of finding the best subset of items to maximize a "diminishing returns" (submodular) function when feedback is noisy and limited (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 this optimal performance, bridging a significant gap in prior research.

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 specific size ($k$) to maximize some outcome (e.g., patient survival, click-through rate). The catch is that you don't know the exact outcome for any given subset beforehand. Instead, you try a subset, get a noisy reward, and have to decide what to try next. Furthermore, the underlying outcome function has a "diminishing returns" property: adding more items to a set yields progressively smaller improvements. This is known as submodularity.

The goal is to minimize "regret" – the difference between the best possible outcome and what the algorithm achieves over time. Previous work had regret bounds that were either too dependent on the number of items ($n$) or too dependent on the subset size ($k$), and a tight theoretical understanding of the optimal trade-off was missing. This paper aims to close this gap by providing a precise minimax lower bound and a matching upper bound for this problem.

Methods

The authors introduce a novel algorithm called SUB-UCB (Submodular Upper Confidence Bound). It's inspired by the "explore-then-commit" strategy, which is common in bandit problems. SUB-UCB intelligently balances exploring different subsets to learn about the unknown function and exploiting the knowledge gained to select better subsets.

A key innovation is how SUB-UCB handles the "greedy" approach to submodular maximization. Instead of strictly following a greedy path for all $k$ items, SUB-UCB uses a more adaptive strategy. It first greedily builds up a subset for a certain number of steps (determined by a parameter $i^*$, which is derived from the theoretical analysis) and then switches to a more comprehensive UCB strategy on larger super-arms. This allows it to adapt to different regimes of the problem, balancing the trade-off between the number of items ($n$) and the subset size ($k$) in its regret.

The theoretical analysis involves constructing "hard instances" of submodular functions to derive a minimax lower bound. This involves carefully designing reward functions for different subsets to make it difficult for any algorithm to distinguish between good and bad choices, thereby establishing a fundamental limit on performance.

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 stress-test the algorithm's performance against the derived lower bounds.

Key Insights and Ideas

  • Bridging the Gap: The paper establishes a new, tighter minimax lower bound for submodular maximization with bandit feedback, resolving a long-standing question about the optimal trade-off between the number of items ($n$) and the subset size ($k$) in the regret.
  • Adaptive Greedy Strategy: SUB-UCB's success comes from its adaptive approach. It doesn't rigidly stick to a greedy strategy for all $k$ items. Instead, it intelligently switches between a greedy phase and a more exhaustive UCB phase, allowing it to perform well across different problem scales.
  • The Role of $i^*$: The parameter $i^*$ (derived from the lower bound analysis) is crucial. It dictates the optimal point to switch from a greedy exploration to a broader UCB exploration, effectively balancing the exploration of smaller subsets versus larger ones.
  • Regret Definition Matters: The paper highlights the importance of using the "robust greedy regret" ($R_{gr}$) as the primary measure, which is more informative than other regret definitions in this context, especially when dealing with noisy observations.

Key Results

  • Minimax Lower Bound: The paper proves a minimax lower bound on regret of $\tilde{\mathcal{O}}(\min_{L \le k} (L^{1/3}n^{1/3}T^{2/3} + \sqrt{n^{k-L}T}))$. This bound precisely characterizes the optimal trade-off between $n$, $k$, and $T$.
  • Algorithm Achieves Optimality: The proposed SUB-UCB algorithm achieves a regret of $\tilde{\mathcal{O}}(\min_{L \le k} (L n^{1/3}T^{2/3} + \sqrt{L}T))$, which matches the derived lower bound up to logarithmic factors. This is the first algorithm to achieve this optimal rate.
  • Improved Lower Bound for Restricted Class: For a slightly restricted class of algorithms, a stronger lower bound of $\tilde{\mathcal{O}}(\min_{L \le k} (L n^{1/3}T^{2/3} + \sqrt{L}T))$ is proven.

Limitations and Future Work

  • Monotonicity Assumption: The current work assumes the submodular function is monotonic (non-decreasing). Extending the results to non-monotonic submodular functions is a significant open problem.
  • General Constraints: The paper focuses on cardinality constraints. Future work could explore similar minimax optimal bounds for other constraints, such as matroid constraints, or for more general offline-to-online greedy procedures.
  • DR-Submodularity and Continuous Settings: The authors suggest that proving similar minimax optimal bounds for DR-submodular optimization or continuous settings (which also have $(1-e^{-1})$-approximation guarantees) would be valuable future research directions.
  • Empirical Validation: While the paper includes experiments, further empirical validation on real-world datasets would be beneficial to demonstrate the practical advantages of SUB-UCB.

Summary updated

Abstract

We consider maximizing a monotonic, submodular set function $f: 2^{[n]} \rightarrow [0,1]$ under stochastic bandit feedback. Specifically, $f$ is unknown to the learner but at each time $t=1,\dots,T$ the learner chooses a set $S_t \subset [n]$ with $|S_t| \leq k$ and receives reward $f(S_t) + \eta_t$ where $\eta_t$ is mean-zero sub-Gaussian noise. The objective is to minimize the learner's regret over $T$ times with respect to ($1-e^{-1}$)-approximation of maximum $f(S_*)$ with $|S_*| = k$, obtained through greedy maximization of $f$. To date, the best regret bound in the literature scales as $k n^{1/3} T^{2/3}$. And by trivially treating every set as a unique arm one deduces that $\sqrt{ {n \choose k} T }$ is also achievable. In this work, we establish the first minimax lower bound for this setting that scales like $\mathcal{O}(\min_{i \le k}(in^{1/3}T^{2/3} + \sqrt{n^{k-i}T}))$. Moreover, we propose an algorithm that is capable of matching the lower bound regret.
BibTeX
@inproceedings{tajdini2024minimax,
  author = {Artin Tajdini and Lalit Jain and Kevin Jamieson},
  title = {{Minimax Optimal Submodular Optimization with Bandit Feedback}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=Vn0FWRImra},
}
Figure