stat.MLNov 17, 2026

Bandit Online Submodular Minimisation Using Zeroth-Order Oracles

Authors: Amir Ali Farzin, Philipp Braun, Iman Shames

Organizations: School of Engineering, Australian National University · Department of Electrical and Electronic Engineering, University of Melbourne

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((1+PN∗)N3/4)O\big((1+\sqrt{P^\ast_N})N^{3/4}\big) in general and O((1+PN∗)N2/3)O\big((1+\sqrt{P^\ast_N})N^{2/3}\big) under a sufficiently small drift, where PN∗P^\ast_N is the path length of the minimiser sequence, together with the corresponding O(N3/4)O(N^{3/4}) and O(N2/3)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.

Figures & tables

Explore similar work

Nov 9, 2026

Efficient Online Submodular Maximization with Bandit Feedback

We study online monotone submodular maximization under a cardinality constraint with bandit feedback. On each round, the learner selects at most kk elements from a ground set of size nn and observes only the value of the selected set. We develop an efficient algorithm achieving O ⁣(knTlog⁡(n/k))O\!\left(k\sqrt{nT\log(n/k)}\right) expected (1−1/e)(1-1/e)-regret over TT rounds. To our knowledge, this is the first polynomial-time algorithm with T\sqrt{T} dependence on the horizon for arbitrary monotone submodular functions in the bandit setting. Our approach uses randomized sampling and a carefully constructed potential to reduce online submodular maximization to online linear optimization over the probability simplex.
Aug 25, 2026

Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy

We study adversarial bandit maximization of monotone submodular functions under a matroid constraint. For a rank-kk matroid on nn elements, we give a randomized oracle-polynomial algorithm that makes one feasible value query per round and has expected (1−1/e)(1-1/e)-regret O~(n1/3k2/3T2/3)\widetilde O(n^{1/3}k^{2/3}T^{2/3}). This is the first sublinear-regret algorithm for adversarial bandit submodular maximization under general matroid constraints. Technically, we view the problem as learning an exchange policy for the Poisson base walk. This connects the problem to contextual bandits and gives an information-theoretic sublinear-regret guarantee, but directly learning the exponentially many policies requires exponential time and space. We therefore introduce balanced fractional exchanges, which compress the policy mixture into a single fractional base while retaining the exchange information needed by the Poisson analysis. This leads to an polynomial time algorithm with the same regret guarantee.
Feb 24, 2026

Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets

We study online maximization of non-monotone Diminishing-Return(DR)-submodular functions over down-closed convex sets, a regime where existing projection-free online methods suffer from suboptimal regret and limited feedback guarantees. Our main contribution is a new structural result showing that this class is 1/e1/e-linearizable under carefully designed exponential reparametrization, scaling parameter, and surrogate potential, enabling a reduction to online linear optimization. As a result, we obtain O(T1/2)O(T^{1/2}) static regret with a single gradient query per round and unlock adaptive and dynamic regret guarantees, together with improved rates under semi-bandit, bandit, and zeroth-order feedback. Across all feedback models, our bounds strictly improve the state of the art.