Anytime Stop-Level Descent for Submodular Bandits with Scalar Feedback

Many recommendation and influence problems ask a learner to pick a set of $k$ items out of $n$ each round and then see only one number: how well the whole set did. Under this "full-bandit" feedback, the best known algorithms for submodular rewards (rewards with diminishing returns, such as coverage or influence spread) all rely on knobs tuned to the time horizon $T$. These knobs include how many times to re-sample each candidate set before trusting its average, how many items to choose greedily before switching to exhaustive search, and how large a random subset to scan at each greedy step. The theory prescribes the scaling of each knob, such as $T^{2/3}$ exploration or a stop level chosen from $T$, $n$ and $k$. The constants in front are hidden inside big-O notation. In practice $T$ is rarely known, and nobody has measured how much regret is lost when the constants are wrong.

This note proposes a single algorithmic change and a measurement study to go with it. The algorithm is an anytime version of the nearly minimax-optimal Sub-UCB method. It starts greedy and gradually "un-commits" its most recent greedy choices, handing them to an exhaustive search as time passes. The key point is that data collected before an un-commit remains valid afterwards, so the learner never restarts. The measurement study characterizes, both analytically and with game-theoretic importance scores, how sensitive existing full-bandit methods are to their horizon-dependent knobs. It then tests whether the new method removes most of what there is to tune.

Core Claim

In full-bandit submodular maximization, the horizon-dependence of exploration parameters is largely a stand-in for two unknown quantities: the size of the marginal-gain gaps, and the elapsed time. The stop level of Nearly Minimax Optimal Submodular Maximization with Bandit Feedback can be driven downward online without any restart. When greedy item $x_l$ is released, every set played in the old exhaustive stage (prefix$_l \cup S'$ with $|S'| = k-l$) is itself an arm of the new exhaustive stage over $k-l+1$ items, because it equals prefix$_{l-1} \cup (\{x_l\} \cup S')$. Its reward samples therefore carry over. The rule for when to release an item combines a confidence test on the greedy step's marginal gap with the elapsed round count.

We claim that this descent keeps Sub-UCB's rate $\tilde{O}(\min_L [L n^{1/3} T^{2/3} + \sqrt{\binom{n}{k-L} T}])$ up to logarithmic factors without knowing $T$. We further claim that it has markedly lower tunability, in the sense of HyperSHAP: little regret is left to recover by tuning its remaining constants. That distinction matters because a method can be insensitive in theory yet still leave large empirical gains on the table.

Why the sensitivity question is not trivial

A back-of-envelope decomposition for explore-then-commit greedy methods shows what is at stake. Let the method re-sample each of $N$ evaluated sets $m = cT^{2/3}$ times, where $c$ is the hidden constant. Worst-case regret then behaves like

$$R(c) \approx \left(A\,c + B\,c^{-1/2}\right) T^{2/3},$$

where $A$ scales with $N$ and counts the rounds spent exploring. $B$ scales with $k$ and counts the loss from committing to a set whose estimate has error $1/\sqrt{m}$. This form is the same bias-variance balance that produces the $T^{2/3}$ barrier in Online Submodular Minimization.

The formula predicts an asymmetry. Over-exploring by a factor of 10 multiplies the first term by 10, while under-exploring by 10 multiplies the second term only by about 3.2. It also predicts that worst-case tuning over-explores on easy instances. When marginal gaps exceed $1/\sqrt{m}$, the commit term effectively vanishes, and the regret-optimal $c$ is far below the theoretical choice. None of C-ETC (A Framework for Adapting Offline Algorithms...), SGB (Combinatorial Stochastic-Greedy Bandit) or Sub-UCB report this curve. Testing it is the first deliverable, and it motivates the gap-adaptive rule.

Research Program

The first part is the sensitivity map. We run C-ETC, SGB, ETCG and Sub-UCB over a grid of their constants: the exploration multiplier, the subset-size multiplier and tolerance $\epsilon$ in SGB, and the stop level $l$ in Sub-UCB. We also vary the horizon supplied to the algorithm relative to the true horizon, from $T/10$ to $10T$. We then fit the decomposition above and check where it breaks.

We treat each algorithm's knobs as players in the tunability game of HyperSHAP, with negative cumulative regret as the payout. HyperSHAP was built for offline hyperparameter optimization on lcbench, rbv2_ranger, PD1 and JAHS-Bench-201. It separates sensitivity (variance across the configuration space) from tunability (gain available over defaults). Its "rule of three" finding says interactions beyond third order are negligible. We test whether that holds for coupled bandit knobs such as SGB's $(s_i, m, \epsilon)$. Our contribution here is applying the method in a sequential-regret setting where it has not been used, not changing the method itself. The evaluations are cheap simulations, so surrogate error is less of a concern than in the original setting.

The second part is the algorithm, which we call Stop-Level Descent. It begins as greedy with UCB-based per-step selection, as in Sub-UCB's greedy stage. The last committed item is released into the exhaustive stage when either of two conditions holds. The first is that its confidence interval still overlaps a competitor's after the round count exceeds $n^{1/3} t^{2/3}$-scaled thresholds. The second is that elapsed time $t$ passes the crossover point where the exhaustive term of the bound becomes cheaper, computed with $t$ in place of $T$.

Released items and their sample histories merge into the exhaustive arm set as described in the core claim. Sets that are new at level $k-l+1$ start with empty statistics. The analysis must bound the regret from those fresh arms plus the greedy-stage regret accumulated before each release. We expect a geometric-sum argument over release times to give the stated rate with a $\log T$ overhead. This is the main theoretical risk.

Baselines

The naive reference point is exhaustive UCB over all $\binom{n}{k}$ sets, which Tajdini et al. show loses at every practical horizon. A second reference is ETCG and SGB run with theory-default constants and a deliberately misstated horizon.

The strongest existing method is Sub-UCB given the true $T$ and the stop level chosen by its own formula. This is an oracle our method cannot beat on its own terms. The success criterion is to come within a small constant factor of it (we target 1.3x in final cumulative regret) at every horizon, without knowing $T$. We also compare against Sub-UCB combined with the doubling trick, and against oracle-tuned Sub-UCB with $l$ chosen after the fact from the grid. Beating doubling-trick Sub-UCB at all horizons, and matching best-in-hindsight $l$ within that factor, counts as success.

A model-selection baseline runs regret balancing (Regret Balancing for Bandit and RL Model Selection) over the $k+1$ Sub-UCB instances $l \in \{0,\dots,k\}$. Each instance is given Sub-UCB's bound as its candidate regret bound, which satisfies that paper's requirement of known candidate bounds.

Two ablations isolate the key ingredient. The first releases items on schedule but discards history at each release, which isolates the value of data carryover. The second uses only the time-based release rule with no confidence test, which isolates the value of gap adaptivity.

All methods run on the same instances and seeds with identical per-round compute. Every method with a tunable constant, including ours, receives the same grid budget, and results are reported both at defaults and at tuned values.

No reported scalar result was found on Lacuna for Sub-UCB, SGB or C-ETC on any benchmark. The papers report plots and qualitative claims, such as SGB being "up to 30 times faster" than ETCG. The only numeric meta-tuning result in the file comes from a linear contextual setting: DOPLINUCB reaches cumulative regret 13,569 against 15,331 for the best fixed exploration parameter on Adult with switches every 1,000 rounds (Hyper-parameter Tuning for the Contextual Bandit). That number is context for the size of tuning gains, not a comparable baseline.

Why not just…?

Why not just use the doubling trick? It preserves the rate but throws away all exploration at each restart, which the C-ETC and SGB authors themselves flag as a limitation. For Sub-UCB it is worse. The optimal $l$ shrinks as $T$ grows, so each restart re-runs a greedy stage the learner should be moving away from. The first ablation (release without carryover) is close to a doubling-trick variant. The direct doubling comparison settles whether carryover matters in practice.

Why not just run regret balancing over the $k+1$ stop levels? This is a real threat, because $M = k+1$ is small and Sub-UCB supplies the candidate bounds that the no-free-lunch theorem requires. Its weakness is that the base instances do not share data. Each one pays its own greedy exploration, and the overhead grows linearly in $M$. Whether that overhead stays below $T^{2/3}$ in practice is exactly what the head-to-head comparison measures. If regret balancing matches Stop-Level Descent, we will report that the simpler method suffices and reframe the contribution as the sensitivity map.

Why not just plug the current round $t$ into Sub-UCB's formula for $l$? Doing so gives a time-varying schedule. Without carryover, however, every decrease in $l$ is a restart, and without a gap test it ignores easy instances where greedy is already correct. The second ablation is exactly this rule plus carryover. If it matches the full method, the confidence test is unnecessary and we drop it.

Why not just use parameter-free FTRL? The self-bounding learning rates of Revisiting Online Submodular Minimization and Parameter-Free Multi-Armed Bandit Algorithms... rest on the convex Lovász extension, which applies to submodular minimization but not maximization. The adaptive-regularizer method also still sits at $O(T^{2/3})$ in the adversarial bandit case. It is not a competitor on this problem.

Proposed Experiments

We will use the synthetic hard instances of Tajdini et al., the unique-greedy-path and weighted set cover problems with tiny marginal gaps, where the best stop level is known to decrease with $T$. We will also use the 534-node Facebook influence graph from SGB and the Million Song budgeted recommendation task from C-ETC, restricted to cardinality constraints. Finally, we will use the Epinions and MovieLens objectives from OSMviaOCO, with rewards perturbed by noise.

Metrics are cumulative $(1-1/e)$-regret against the offline greedy value, as anytime curves. We report the ratio to oracle-tuned Sub-UCB across $T \in [10^3, 10^6]$, the regret-versus-constant curves, and HyperSHAP tunability values per knob.

Three checks are decisive. First, the fitted sensitivity curves must show the predicted asymmetry, with over-exploration costing more than under-exploration, and a gap-dependent optimum well below the theory default on easy instances. If they do not, the motivation for gap adaptivity weakens. Second, Stop-Level Descent must stay within the target factor of oracle Sub-UCB at every horizon while doubling-trick Sub-UCB does not. Third, its total tunability, meaning regret recovered by tuning its constants, must be a small fraction of what tuning recovers for Sub-UCB with a misstated $T$.

Failing the second check while passing the first would still be a useful negative result. It would mean the $T$-dependence is intrinsic rather than a proxy for unknown gaps.