Research map / Learning theory and algorithms / Combinatorial and search optimization
Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Trains a single set-conditioned "greedy policy" with REINFORCE-style updates so that greedy batch selection for expensive multi-objective combinatorial optimization can be parallelized, and optimizes batch acquisition directly in combinatorial space.
Problem
Selecting a proposal batch in active learning for expensive multi-objective combinatorial optimization is a subset selection problem with huge search space; prior LSO and individual-score methods ignore batch interdependencies or optimize in a mismatched latent space, and greedy methods are hard to
Approach
A set-conditioned policy is trained so that its own greedy sampling reproduces exact greedy subproblem solutions (the "greedy policy"), letting all n greedy subproblems be addressed by one policy; the batch is built by sequential sampling from this policy with a best-of-l selection by marginal gain. Also extends approximation bounds to near-submodular and sum-dispersion diversity functions.
Key results
- On RFP batch BO, the method with MLM reaches the same Hypervolume as baselines with 1.69x fewer queries and ~25% higher relative Hypervolume than best baseline (MBGA).
- In single-round bigram subset selection, the method matches exact greedy at 2 bigrams and beats PC-RL and greedy+RL baselines across cardinalities.
- On first-round NEHVI, the method scores 0.779 on RFP vs 0.654 for MBGA and 0.591 for LaMBO.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the greedy-policy subset selection method instead of preference-conditioned RL (TS) | Subset selection · 2 Bigrams | Hypervolume: 0.558 (0.007) -> 0.568 (0.000) | Helped |
| Use the greedy-policy subset selection method instead of exact greedy | Subset selection · 3 Bigrams | Hypervolume: 0.350 -> 0.329 | Hurt |
| Use the greedy-policy subset selection method instead of exact greedy | Subset selection · 2 Bigrams | Hypervolume: 0.568 -> 0.568 | No clear effect |
| Use the greedy-policy method instead of preference-conditioned RL (TS) | DNA aptamer subset selection · DNA aptamer, n=4 | Hypervolume: 0.515 (0.041) -> 0.662 (0.019) | Helped |
| Use the greedy-policy method instead of the best listed baseline | First-round batch BO · RFP | NEHVI: 0.654 (0.052) -> 0.779 (0.045) | Helped |
| Use the greedy-policy method instead of the best listed baseline | First-round batch BO · 3 Bigrams | NEHVI: 12.376 (1.576) -> 16.444 (1.529) | Helped |
| Use the greedy-policy method instead of the best listed baseline | First-round batch BO · Molecules | NEHVI: 0.545 (0.064) -> 0.698 (0.104) | Helped |
| Use Ours with MLM instead of the best baseline, MBGA | RFP multi-round active learning · RFP | relative Hypervolume: 25% higher | Helped |
| Use Ours with MLM instead of baseline methods | RFP multi-round active learning · RFP | queries to comparable performance: 1.69 times fewer queries | Helped |
Limitations
- Theoretical convergence assumes conditions on the objective that may not hold in practice (authors acknowledge)
- Bounds rely on submodularity ratio or alpha-approximation that are not directly verified in experiments
- Batch BO baselines required reimplementation fixes; comparisons depend on matched query budgets
Experimental setup
Datasets: bigram matching synthetic tasks DNA aptamer design task (NUPACK) red fluorescent protein (RFP) task small molecules task
Benchmarks: bigram matching tasks DNA aptamer design RFP multi-round active learning RFP / 3 Bigrams / Molecules first-round NEHVI
Metrics: Hypervolume indicator NEHVI value number of queries to match baseline
Baselines: LaMBO MBGA AL-MOGFN NSGA-II PC-RL (TS) PC-RL (WS) Greedy + RL Greedy + HC Greedy + RS
Builds on: LaMBO preference-conditioned RL approximate greedy algorithm REINFORCE
Closest papers by meaning
- Divide and Learn: Multi-Objective Combinatorial Optimization at Scale (ICML 2026 · similarity 0.89)
- Pareto Front-Diverse Batch Multi-Objective Bayesian Optimization (AAAI 2024 · similarity 0.86)
- Amortized Active Generation of Pareto Sets (NeurIPS 2025 · similarity 0.85)
- Efficient Biological Data Acquisition through Inference Set Design (ICLR 2025 · similarity 0.85)
- Batched Energy-Entropy acquisition for Bayesian Optimization (NeurIPS 2024 · similarity 0.85)
- Accelerating data-driven algorithm selection for combinatorial partitioning problems (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.