将大规模多目标组合优化转化为可扩展的在线学习问题，实现高效精准求解。
Divide and Learn: Multi-Objective Combinatorial Optimization at Scale
- 分解决策空间，逐位解决带宽问题，提升求解效率。
- 在标准测试中达到专用求解器80%~98%性能，采样效率提升百倍以上。
- 适合高维、多目标、评估成本高的真实场景，如AI加速器设计。
多目标组合优化需在指数级离散空间中寻找帕累托最优解，现有方法在通用性、可扩展性或理论保证上存在短板。本文将问题重构为分解决策空间上的在线学习任务，通过自适应专家引导的序列构造解决位置相关的老虎机子问题。该方法的后悔界为 $O(d oot\text{}}{T \log T})$，仅依赖子问题维度 $d$ 而非组合空间规模。在标准基准测试中，本方法性能达专用求解器的80%–98%，采样与计算效率较贝叶斯优化提升两到三个数量级。在涉及昂贵仿真的真实世界软硬件协同设计（如AI加速器）中，于固定评估预算下优于对比方法，且优势随问题规模和目标数增加而扩大，确立了基于分解空间的老虎机优化作为替代代理建模或离线训练的可靠范式。
原文摘要 · Abstract (English)
Multi-objective combinatorial optimization seeks Pareto-optimal solutions over exponentially large discrete spaces, yet existing methods sacrifice generality, scalability, or theoretical guarantees. We reformulate it as an online learning problem over a decomposed decision space, solving position-wise bandit subproblems via adaptive expert-guided sequential construction. This formulation admits regret bounds of $O(d\sqrt{T \log T})$ depending on subproblem dimensionality \(d\) rather than combinatorial space size. On standard benchmarks, our method achieves 80--98\% of specialized solvers performance while achieving two to three orders of magnitude improvement in sample and computational efficiency over Bayesian optimization methods. On real-world hardware-software co-design for AI accelerators with expensive simulations, we outperform competing methods under fixed evaluation budgets. The advantage grows with problem scale and objective count, establishing bandit optimization over decomposed decision spaces as a principled alternative to surrogate modeling or offline training for multi-objective optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。