Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning Robust Search Strategies Using a Bandit-Based Approach
Wei Xia, Roland Yap
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| select variable-ordering heuristics online with UCB1 rather than use a fixed individual heuristic | CSP solving · 256 instances solved by all heuristics | mean runtime ratio to VBS: 3.5 | Improved |
| select variable-ordering heuristics online with UCB1 rather than use a fixed individual heuristic | CSP solving · 256 instances solved by all heuristics | maximum runtime ratio to VBS: 120.7 | Improved |
| use online bandit selection instead of random-arm selection | CSP solving · CSP benchmark instances | runtime | Improved |
| use UCB1 instead of dynamic UCB1-100 (ablation) | MAB-based CSP search · CSP benchmark instances | runtime | Improved |
| use UCB1 instead of dynamic TS-500 (ablation) | MAB-based CSP search · CSP benchmark instances | runtime | Mixed |
| use one MAB selector for the whole search tree instead of multiple selectors by search level (ablation) | MAB-based CSP search · CSP benchmark instances | performance | No clear effect |
| use MAB-UCB1 rather than sPSS sequential decomposition and sampling | CSP solving · rand3-20-20-1 | explored search nodes: 507K -> 73K | Improved |
| use UCB1 rather than sPSS sequential decomposition and sampling | CSP solving · ruler-34-9-a4 | runtime: 116.8s -> 6.9s | Improved |
| use dynamic sliding-window variants rather than non-dynamic UCB1 (ablation) | MAB-based CSP search · selected benchmark series | runtime | Hurt |
Closest papers by meaning
- Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model (ICML 2024 · similarity 0.84)
- Teacher-Aware Evolution of Heuristic Programs from Learned Optimization Policies (NeurIPS 2026 · similarity 0.84)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.84)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.84)
- Prediction-Based Adaptive Variable Ordering Heuristics for Constraint Satisfaction Problems (AAAI 2025 · similarity 0.83)
- Multi-Objective Evolution of Heuristic Using Large Language Model (AAAI 2025 · similarity 0.83)
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.
