研究带反馈图的纯探索问题，提出最优算法并分析样本复杂度。
Pure Exploration with Feedback Graphs
- 基于反馈图设计新型纯探索算法，刻画信息传递机制。
- 揭示样本复杂度与图结构相关量的依赖关系，给出下界。
- 适用于未知随机反馈图场景，适合在线学习研究者。
我们研究了在反馈图约束下的在线学习中纯探索问题的样本复杂度。该反馈图决定了学习者可获得的信息，覆盖从完全信息、纯老虎机反馈到无选择动作反馈等多种情形。尽管此类问题在损失最小化中已有研究，但纯探索设置尚未被探讨。本文推导出在固定置信度下识别最优动作的实例相关下界，即使反馈图未知且为随机情况；并给出伯努利奖励下的不可识别性结果。此外，我们的发现揭示了样本复杂度如何随图相关量变化。最后，提出渐近最优算法TaS-FG（Track and Stop for Feedback Graphs），并在不同图配置下验证其高效性。
原文摘要 · Abstract (English)
We study the sample complexity of pure exploration in an online learning problem with a feedback graph. This graph dictates the feedback available to the learner, covering scenarios between full-information, pure bandit feedback, and settings with no feedback on the chosen action. While variants of this problem have been investigated for regret minimization, no prior work has addressed the pure exploration setting, which is the focus of our study. We derive an instance-specific lower bound on the sample complexity of learning the best action with fixed confidence, even when the feedback graph is unknown and stochastic, and present unidentifiability results for Bernoulli rewards. Additionally, our findings reveal how the sample complexity scales with key graph-dependent quantities. Lastly, we introduce TaS-FG (Track and Stop for Feedback Graphs), an asymptotically optimal algorithm, and demonstrate its efficiency across different graph configurations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。