提出带图反馈的组合半赌局模型，提升奖励观测效率。
Adversarial Combinatorial Semi-bandits with Graph Feedback
- 用反馈图结构设计新型观测机制，仅需观察邻近臂的奖励。
- 最优后悔界为~Θ(S√T + √αST)，优于传统半赌局和全信息情形。
- 适用于大规模组合决策场景，如推荐系统与资源分配。
在组合半赌局中，学习者反复从组合臂集合中选择，获得所选臂奖励之和，并观测每个被选臂的实际奖励。本文将该框架扩展至包含图反馈：学习者可观测所选臂在反馈图 $G$ 中所有邻居臂的奖励。我们证明，在时间跨度 $T$ 内，最优后悔率呈 ~Θ(S√T + √αST) 形式，其中 $S$ 为组合决策规模，$α$ 为图 $G$ 的独立数。该结果在全信息（$G$ 为完全图）下的 ~Θ(S√T) 与半赌局反馈（$G$ 仅含自环）下的 ~Θ(√KST) 之间插值，$K$ 为总臂数。关键技术在于利用具有负相关性的随机决策向量实现凸化动作。此外，我们指出仅以期望方式实现凸化动作的在线随机镜像下降（OSMD）方法存在性能缺陷。最后，我们引入一般容量下的组合半赌局问题，并基于本研究推导出更优的后悔上界，可能具独立研究价值。
原文摘要 · Abstract (English)
In combinatorial semi-bandits, a learner repeatedly selects from a combinatorial decision set of arms, receives the realized sum of rewards, and observes the rewards of the individual selected arms as feedback. In this paper, we extend this framework to include \emph{graph feedback}, where the learner observes the rewards of all neighboring arms of the selected arms in a feedback graph $G$. We establish that the optimal regret over a time horizon $T$ scales as $\widetildeΘ(S\sqrt{T}+\sqrt{αST})$, where $S$ is the size of the combinatorial decisions and $α$ is the independence number of $G$. This result interpolates between the known regrets $\widetildeΘ(S\sqrt{T})$ under full information (i.e., $G$ is complete) and $\widetildeΘ(\sqrt{KST})$ under the semi-bandit feedback (i.e., $G$ has only self-loops), where $K$ is the total number of arms. A key technical ingredient is to realize a convexified action using a random decision vector with negative correlations. We also show that online stochastic mirror descent (OSMD) that only realizes convexified actions in expectation is suboptimal. In addition, we describe the problem of \emph{combinatorial semi-bandits with general capacity} and apply our results to derive an improved regret upper bound, which may be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。