Bandit Online Submodular Minimisation Using Zeroth-Order Oracles

Amir Ali Farzin, Philipp Braun, Iman ShamesarXiv 2026 · arXiv

TL;DR

This paper introduces the first algorithm with dynamic regret guarantees for online submodular minimization under bandit feedback. By leveraging a novel two-point zeroth-order oracle and a clever "common threshold" rounding technique, the authors provide a way to track a moving optimal solution in real-time, significantly outperforming existing static-benchmark methods in non-stationary environments.

What Problem Does This Paper Address?

Imagine you are deploying sensors in a forest to detect wildfires. The "value" of adding a sensor depends on which sensors are already there—this is submodularity (the principle of diminishing marginal returns). In an online setting, the environment changes (e.g., wind patterns shift), meaning the ideal sensor locations change over time.

The challenge is bandit feedback: you only observe the cost/benefit of the specific set of sensors you deployed, not the "what ifs" of every other possible combination. Most existing algorithms for this problem focus on static regret, which compares your performance to the single best fixed set of sensors for the entire duration. However, if the optimal set is moving, a static benchmark is too weak. This paper tackles dynamic regret, aiming to keep up with the best possible set at every time step.

Methods

The authors bridge the gap between discrete set selection and continuous optimization using the Lovász extension, which allows a submodular set function to be treated as a convex function over a unit hypercube.

To optimize this without direct access to gradients (since we only have bandit feedback), they use Zeroth-Order (ZO) Optimization. Key technical contributions include:

  • Two-Point Threshold Oracle: Instead of querying one point, the algorithm queries two nearby points ($x$ and a perturbed $x + \mu u$).
  • Common Random Thresholding: To turn continuous points back into discrete sets (which can actually be "played" in the bandit setting), they use a random threshold $\tau$. Crucially, they use the same $\tau$ for both points in the two-point estimate. This coupling makes the base evaluation act as a "control variate," drastically reducing variance.
  • Unit Ball Smoothing: They draw smoothing directions from a unit sphere rather than a Gaussian distribution. This ensures the perturbed points stay within a bounded range, allowing for a fixed threshold range $[-\mu, 1+\mu]$ that guarantees the estimator remains unbiased.

Datasets

The paper evaluates the algorithm using a synthetic numerical example designed to simulate a non-stationary environment:

  • The Function: A time-varying submodular function combining a concave "coverage" term and a modular "reward" term that fluctuates via a sine wave.
  • The Goal: Induce a "moving minimizer" where the optimal subset changes periodically.
  • Baseline: They compare against the landmark algorithm by Hazan and Kale (2012) and a Gaussian variant of their own method.

Key Insights and Ideas

  • Tracking vs. Converging: Traditional bandit methods for submodular minimization (like Hazan and Kale) often update only one coordinate at a time. This is fine for finding a static target but fails when the target moves. The proposed ZO method updates all coordinates every iteration, allowing it to "chase" the moving optimal solution more effectively.
  • The Power of the Base Evaluation: The "base play" (the second point in the two-point oracle) isn't just extra data; it's a variance reduction tool. Ablation studies showed that without this base evaluation, the regret explodes.
  • Smoothing Matters: While Gaussian smoothing is common in ZO optimization, it creates unbounded perturbations. In the world of submodular sets (where you are confined to the $[0, 1]$ hypercube), unit ball smoothing is mathematically superior because it keeps the "probes" within a predictable, roundable range.

Key Results

  • Theoretical Bounds: The authors establish dynamic regret bounds of $O(N^{3/4})$ in general and $O(N^{2/3})$ under "small drift" conditions (where the cost functions don't change too violently between steps).
  • Numerical Superiority: In simulations with a moving minimizer, the proposed algorithm achieved a final dynamic regret of approximately 71,209, compared to 102,466 for the Hazan and Kale baseline.
  • Path Length Sensitivity: The advantage of this new method grows as the "path length" (how much the optimal solution moves) increases. When the minimizer is stationary, the methods perform similarly; as the environment becomes more volatile, the new method shines.

Limitations and Future Work

  • Lower Bounds: It remains an open question whether a matching $\Omega(N^{2/3})$ lower bound exists for the static regret in this specific bandit setting.
  • The Gaussian Mystery: Interestingly, in experiments, a Gaussian variant of their algorithm actually performed the best, even though the current theoretical analysis doesn't fully cover it due to the complexities of rounding unbounded perturbations.
  • Complexity: The current analysis assumes submodularity is strictly maintained. Future work could explore "approximately" submodular functions or more complex min-max (adversarial) settings.

Summary updated

Abstract

We consider online submodular minimisation under bandit feedback, where at each round a decision maker plays a subset and observes only its cost, while the cost functions, and hence their minimiser, change over time. Existing bandit methods only guarantee static regret, which compares against a single fixed subset and is a weak benchmark when the minimiser moves. This paper provides, to the best of our knowledge, the first method with guarantees for tracking a moving minimiser in this setting. We propose a zeroth-order method built on a two-point oracle for the Lovász extension whose two evaluations are both subsets that can be played. The perturbed and base points are rounded by a common random threshold, and drawing the smoothing direction from the unit sphere makes the base evaluation a zero-mean control variate, so the oracle is an unbiased estimator of the smoothed gradient. We establish dynamic regret bounds of order $O\big((1+\sqrt{P^\ast_N})N^{3/4}\big)$ in general and $O\big((1+\sqrt{P^\ast_N})N^{2/3}\big)$ under a sufficiently small drift, where $P^\ast_N$ is the path length of the minimiser sequence, together with the corresponding $O(N^{3/4})$ and $O(N^{2/3})$ static regret bounds. Numerically, the method attains lower regret than the algorithm of (Hazan and Kale (2012)), with the advantage growing with the path length.
BibTeX
@misc{farzin2026bandit,
  author = {Amir Ali Farzin and Philipp Braun and Iman Shames},
  title = {{Bandit Online Submodular Minimisation Using Zeroth-Order Oracles}},
  year = {2026},
  eprint = {2611.22130},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22130},
}
Figure