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) in general and O((1+PN∗)N2/3) under a sufficiently small drift, where PN∗ is the path length of the minimiser sequence, together with the corresponding O(N3/4) and O(N2/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
Figure 1: Cumulative dynamic regret (left) and static regret (right) against the number of plays.
Figure 2: Iterate optimality gap fkL(xk)−minSfk(S) against the number of plays.
Figure 3: Final dynamic regret vs. PN∗ (left), and its increase over the near-stationary case (right).
We study online monotone submodular maximization under a cardinality constraint with bandit feedback. On each round, the learner selects at most k elements from a ground set of size n and observes only the value of the selected set. We develop an efficient algorithm achieving O(knTlog(n/k)) expected (1−1/e)-regret over T rounds. To our knowledge, this is the first polynomial-time algorithm with 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.
We study adversarial bandit maximization of monotone submodular functions under a matroid constraint. For a rank-k matroid on n elements, we give a randomized oracle-polynomial algorithm that makes one feasible value query per round and has expected (1−1/e)-regret O(n1/3k2/3T2/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.
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/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) 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.
Yiyang Lu, Haresh Jadav, Mohammad Pedramfar +2
Purdue University, West Lafayette, IN, USA · IIT Indore, MP, India · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada