提出应对双目标优化噪声的新框架，实现无假设下的在线决策
A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback
- 定义双目标鲁棒性指标，量化噪声下近似性能退化
- 在线算法实现次线性后悔与约束违反，阶为 $\tilde{O}(δ^{2/3}\texttt{N}^{1/3}T^{2/3})$
- 适用于无结构假设的各类贪心算法，适合实际噪声环境
研究在噪声函数评估下的双目标组合优化问题。尽管单目标场景中已存在鲁棒性与黑箱离线到在线转换的研究，但将这些思想拓展至双目标问题时，因目标与约束的近似保证相互耦合而带来新挑战。本文引入 $(α,β,δ,\texttt{N})$-鲁棒性概念，刻画在有界（可能最坏情况）查询噪声下联合近似保证的退化行为，并提出一个通用黑箱框架，可将任意鲁棒的离线算法转化为双目标组合多臂老虎机的在线算法，且无需线性、子模性或半带反馈等结构假设。所得在线算法的后悔与累积约束违反均为次线性，阶为 $\tilde{O}(δ^{2/3}\texttt{N}^{1/3}T^{2/3})$。通过证明若干经典贪心算法在子模优化中的鲁棒性，展示了该框架的适用性。
原文摘要 · Abstract (English)
We study bi-criteria combinatorial optimization under noisy function evaluations. While resilience and black-box offline-to-online reductions have been studied in single-objective settings, extending these ideas to bi-criteria problems introduces new challenges due to the coupled degradation of approximation guarantees for objectives and constraints. We introduce a notion of $(α,β,δ,\texttt{N})$-resilience for bi-criteria approximation algorithms, capturing how joint approximation guarantees degrade under bounded (possibly worst-case) oracle noise, and develop a general black-box framework that converts any resilient offline algorithm into an online algorithm for bi-criteria combinatorial multi-armed bandits with bandit feedback. The resulting online guarantees achieve sublinear regret and cumulative constraint violation of order $\tilde{O}(δ^{2/3}\texttt{N}^{1/3}T^{2/3})$ without requiring structural assumptions such as linearity, submodularity, or semi-bandit feedback on the noisy functions. We demonstrate the applicability of the framework by establishing resilience for several classical greedy algorithms in submodular optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。