首次实现全反馈下k-子模优化的亚线性误差，突破传统瓶颈。
Stochastic $k$-Submodular Bandits with Full Bandit Feedback
- 用离线转在线框架将经典算法扩展到在线场景
- 在五类约束下均获得与离线最优比对应的亚线性α-后悔
- 证明了离线算法对噪声的鲁棒性，适用于动态决策
本文首次为具有全反馈的在线k-子模优化问题提供了亚线性α-后悔界，其中α是相应的离线近似比。我们提出了针对多类随机组合多臂老虎机问题的在线算法，包括：(i) 单个规模约束的单调函数，(ii) 有拟阵约束的单调函数，(iii) 有拟阵约束的非单调函数，(iv) 无约束的非单调函数，以及 (v) 无约束的单调函数。通过Nie等（2023a）提出的离线转在线框架，将离线k-子模最大化算法转化为在线算法。本工作关键贡献在于分析了离线算法的鲁棒性。
原文摘要 · Abstract (English)
In this paper, we present the first sublinear $α$-regret bounds for online $k$-submodular optimization problems with full-bandit feedback, where $α$ is a corresponding offline approximation ratio. Specifically, we propose online algorithms for multiple $k$-submodular stochastic combinatorial multi-armed bandit problems, including (i) monotone functions and individual size constraints, (ii) monotone functions with matroid constraints, (iii) non-monotone functions with matroid constraints, (iv) non-monotone functions without constraints, and (v) monotone functions without constraints. We transform approximation algorithms for offline $k$-submodular maximization problems into online algorithms through the offline-to-online framework proposed by Nie et al. (2023a). A key contribution of our work is analyzing the robustness of the offline algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。