Learning When to Fear Costs: Adaptive Distortion Schedules for Utility-Minus-Cost Selection

Many selection problems in machine learning ask for a set of items whose benefit shows diminishing returns (each extra sensor, feature, or seed user helps less than the last) but whose price is paid in full. Examples include choosing sensors while paying per measurement, choosing seed users while paying per contact, and choosing training examples while paying for labels. The objective is benefit minus cost, and it is non-monotone: adding an item can make the total worse. Plain greedy selection, which always takes the item with the best immediate net gain, can be arbitrarily bad here. The best practical fix, distorted greedy, shrinks the benefit term early in the run so that the algorithm is wary of expensive items. It shrinks it on a fixed geometric timetable tied to a constant, the submodularity ratio $\gamma$, which measures how close the benefit is to having diminishing returns and is unknown in practice.

We propose to let a reinforcement-learning agent learn that timetable. At each step the agent looks at the current partial set and the spread of candidate gains and costs, and decides how much to distrust the benefit term. We keep the provable guarantee of the original method by always also running the analytical schedule and returning the better of the two sets. The question is concrete. Does a learned, state-dependent caution schedule reliably beat the best fixed schedule on realistic benefit-minus-cost problems? And does the agent discover something interpretable, such as estimating $\gamma$ on the fly from the gains it observes?

Core Claim

Submodular Maximization Beyond Non-negativity maximizes $f(S)=g(S)-c(S)$. Here $g$ is a non-negative, $\gamma$-weakly submodular benefit and $c$ is an additive (per-item) cost, and the constraint is a cardinality limit $|S|\le k$. At step $i$ of $k$, the algorithm adds the item that maximizes the surrogate

$$\Phi_i(T)=\Big(1-\tfrac{\gamma}{k}\Big)^{k-i} g(T) - c(T).$$

It guarantees $\mathbb{E}[g(S)-c(S)] \ge (1-e^{-\gamma}-\epsilon)\,g(OPT) - c(OPT)$. When $\gamma$ is unknown, it falls back on a geometric sweep over $\gamma$. We replace the fixed factor with a learned weight $w_i=\pi_\theta(s_i)\in[0,1]$, where $\pi_\theta$ is a small policy network and $s_i$ is a feature summary of the partial set at step $i$. The item chosen at step $i$ then maximizes $w_i\,\Delta g(x\mid S_{i-1}) - c(x)$, and the agent may also choose to stop early. Returning the better of the learned set and the distorted-greedy set gives the learned method the same worst-case bound, at a little under twice the oracle cost.

The claim is empirical and falsifiable. On heterogeneous-cost instance families, the learned schedule should achieve higher net value than distorted greedy run with the best $\gamma$ chosen per instance in hindsight, at matched oracle calls. This advantage should be largest exactly when cost-to-benefit ratios vary a lot across items.

This differs from the closest RL work in what is learned. Submodular Reinforcement Learning trains policies on marginal-gain rewards, but only for monotone trajectory objectives in control tasks. It neither handles negative marginals nor learns selection algorithms. Learning Combinatorial Optimization Algorithms over Graphs learns which node to add next by Q-learning over graph embeddings, and it offers no guarantee. Our agent picks one scalar per step inside an algorithm whose analysis already exists. That is a much lower-dimensional action, which directly targets the high-variance credit assignment identified as an open problem for learned combinatorial heuristics.

Research Program

The policy sees features that do not depend on the problem family. These are the step fraction $i/k$, the empirical decay rate of accepted benefit gains (a running proxy for $\gamma$ and for curvature), and quantiles of candidate $\Delta g$, $c$, and $\Delta g/c$. It also sees the current net value and the fraction of candidates with positive net gain.

Training uses proximal policy optimization. The reward is the terminal net value normalized by the distorted-greedy value on the same instance, so the agent is explicitly rewarded for beating its own fallback. For speed, candidate gains are evaluated with the random-subsample trick of stochastic distorted greedy, which also makes oracle calls comparable across methods.

The program has three stages.

The first stage builds instance generators. Each generator draws graphs, datasets, and cost distributions from a benchmark family and controls cost heterogeneity separately from benefit curvature. This lets us test when adaptivity helps at all.

The second stage trains on small instances and tests on larger and shifted ones.

The third stage interprets the learned schedules. We regress $w_i$ on the features and ask two questions. Does the agent rediscover the geometric form $(1-\gamma/k)^{k-i}$ with an instance-specific $\gamma$ estimated online? Or does it condition on something the analysis ignores, such as the cost distribution of the items still available?

A second, smaller thread tests whether the approach carries over to a setting without a cardinality limit, where the natural analytical competitor changes. For that unconstrained variant we compare against double-greedy-style randomized rules, in the spirit of those adapted in Randomized Greedy Learning.

Baselines

The naive reference is plain greedy on $g-c$, stopping when the best net gain turns negative. Submodular Maximization Beyond Non-negativity shows this can reach only an $O(1/k)$ fraction of optimal, and it is what practitioners actually run.

The strongest analytical competitor is distorted greedy and its stochastic variant from the same paper, run in two versions. One uses the paper's geometric $\gamma$-sweep. The other uses a per-instance oracle $\gamma$ picked in hindsight from a fine grid. The oracle version is an upper bound on any fixed-shape schedule, which makes it the fairest target. Beating it means a statistically significant gain in mean normalized net value across test instances, measured with paired comparisons on identical instances, with total oracle calls matched. The learned method's calls include both the learned run and the fallback run. We found no reported empirical net-value numbers on Lacuna for distorted greedy on Boston Housing or Email EU; the file lists only its guarantee and runtime. We will therefore reproduce it ourselves.

The strongest tuning-based competitor fits a two- or three-parameter family of schedules, such as $w_i=(1-a)^{b(k-i)}$ with a stopping threshold, on the training instances. The fit uses Bayesian optimization with the same wall-clock budget spent on RL training.

A generic learned heuristic in the style of Learning Combinatorial Optimization Algorithms over Graphs selects items directly, trained on the same data and budget. It tests whether constraining the agent to a distortion weight helps or hurts.

For knapsack-style variants we add Bring Your Own Greedy+Max. That paper reports that on real data its method "often achieves 60-70% accuracy." That result is for a monotone knapsack setting, not ours, so it serves only as context.

Two ablations isolate the key ingredient. One is the learned schedule without the fallback, which measures how often the fallback wins and whether the guarantee is doing any work. The other is the learned schedule with the $\gamma$-proxy features removed, which tests whether online estimation of $\gamma$ is where the gain comes from.

Why not just…?

Why not just tune $\gamma$ or a parametric schedule offline? This is the real threat. If a well-tuned fixed schedule matches the learned policy, state-dependence adds nothing and the proposal should be abandoned in favor of the simpler tuning. The per-instance oracle-$\gamma$ and Bayesian-optimized-family baselines are designed to settle this. We predict a gap only on high-cost-heterogeneity families, where the right amount of caution depends on which items remain. If the gap does not appear there, the claim fails.

Why not just learn item selection end to end, as in S2V-DQN? Learning Combinatorial Optimization Algorithms over Graphs shows free-form learned greedy works well on vertex cover. However, it offers no worst-case bound, and learned policies are known to fail on shifted instances. In addition, a per-item action space makes credit assignment far noisier than one scalar per step. The direct-selection baseline measures both effects: in-distribution value and degradation under size and cost shift.

Why not just run distorted greedy followed by local search? Swap-based improvement after construction is cheap and could recover much of any gap. We include distorted greedy plus a swap search with matched oracle calls as a baseline. If it matches the learned schedule, the practical contribution shrinks to interpretability. The limits of simple swap neighborhoods reported in Deep RL Guided Improvement Heuristic for JSSP suggest, but do not prove, that post-hoc local search alone will fall short.

Proposed Experiments

We use the benefit-minus-cost benchmarks from Submodular Maximization Beyond Non-negativity: Bayesian A-optimal feature selection with measurement costs on Boston Housing, and directed vertex cover minus edge costs on Email EU. We add graph coverage with node costs on ego-Facebook and com-DBLP, following Bring Your Own Greedy+Max, and a MovieLens diversity-minus-cost objective built with data from neu-spiral/OSMviaOCO.

The metrics are net value normalized by the best known value, the oracle calls used, and the fraction of instances on which the fallback wins. For small instances, the best known value is exact, computed by exhaustive search or an integer program. For large instances, it is the best value from long multi-start local search.

We run three decisive checks. The first compares the learned policy with per-instance oracle $\gamma$ across a sweep of cost heterogeneity, and we expect the gap to grow with heterogeneity. The second trains on 200-node graphs and tests on 2,000-node graphs and on adversarial families built to trap greedy, where the fallback should visibly carry the guarantee. The third fits the learned $w_i$ against the geometric form to see whether the agent has recovered, and possibly improved on, the analytical schedule.