解决随机不可用动作下的在线组合优化问题，提升实际场景适应性。
Online combinatorial optimization with stochastic decision sets and adversarial losses
- 基于扰动领导者预测法设计新算法，处理动作随机失效情况。
- 提出计数休眠时间损失估计技术，实现更优后悔界。
- 适用于多种反馈设置，尤其在随机休眠带权问题上性能显著提升。
大多数序列学习研究假设动作集始终固定可用，但现实中传感器读数可能失效、道路段被封锁或商品缺货，导致复合动作随机不可用。本文研究能应对此类不确定性的学习算法，提出基于扰动领导者预测方法的算法，适用于不同反馈机制：全信息、（半）贝叶斯及一种介于二者之间的受限信息设置。核心创新为提出名为「计数休眠时间」的损失估计技术。理论分析给出各类设置下的后悔界，并在具有随机可用性的睡眠贝叶斯问题中，实现当前最高效算法的最佳性能保证的显著提升。实验验证表明，所提算法优于现有方法。
原文摘要 · Abstract (English)
Most work on sequential learning assumes a fixed set of actions that are available all the time. However, in practice, actions can consist of picking subsets of readings from sensors that may break from time to time, road segments that can be blocked or goods that are out of stock. In this paper we study learning algorithms that are able to deal with stochastic availability of such unreliable composite actions. We propose and analyze algorithms based on the Follow-The-Perturbed-Leader prediction method for several learning settings differing in the feedback provided to the learner. Our algorithms rely on a novel loss estimation technique that we call Counting Asleep Times. We deliver regret bounds for our algorithms for the previously studied full information and (semi-)bandit settings, as well as a natural middle point between the two that we call the restricted information setting. A special consequence of our results is a significant improvement of the best known performance guarantees achieved by an efficient algorithm for the sleeping bandit problem with stochastic availability. Finally, we evaluate our algorithms empirically and show their improvement over the known approaches.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。