提出新算法实现图反馈上下文老虎机的近最优后悔率，突破了传统方法对上下文数量的依赖。
Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback
- 设计基于悲观修正与损失转移的在线学习算法，解决无自环臂观测概率过低问题。
- 在固定强可观测图下实现期望后悔率 $ ilde{O}( oot{2}{αT})$，消除对上下文数的多项式依赖。
- 适用于对抗性损失和复杂图结构，适合研究强化学习与市场机制设计的学者。
重复的一价拍卖是具有截断但可重用反馈的上下文决策问题：提交出价后，学习者可推断相关出价的结果，并在不同私有价值下评估它们。这一结构启发了带图反馈的交叉学习上下文老虎机，其中执行一个动作会揭示其所有外邻接动作在每种情境下的损失。一个核心开放问题是：在独立同分布的情境和固定强可观测反馈图（独立数为 $\alpha$）下，能否消除对上下文数量的多项式依赖，同时达到经典图老虎机的速率 $\tilde{O}(\sqrt{\alpha T})$？该问题甚至在随机损失和每个动作带有自环的图中仍悬而未决。本文在更强的盲从对抗损失模型下，对所有强可观测图（包括无自环的动作）给出了肯定回答。主要障碍在于：频繁被选择但无自环的动作可能有趋近零的观测概率。我们的算法在每个周期隔离一个此类动作，使用悲观修正抵消一阶估计偏差，并在FTRL分析中转移损失以控制二次项。最终实现了期望后悔率 $\tilde{O}(\sqrt{\alpha T})$。受控合成实验验证了图反馈与交叉学习结合的优势，并展示了 $T$ 和 $\alpha$ 的预期缩放关系。主定理在 Lean 中以超过 10 万行代码的形式完整形式化。形式化及实验数据可在 GitHub 仓库获取：https://github.com/RuiyuanHuang/graphical-cross-learning-review-artifact。
原文摘要 · Abstract (English)
Repeated first-price auctions are contextual decision problems with censored but reusable feedback: after submitting a bid, a learner can infer the outcomes of related bids and evaluate them under different private values. This structure motivates cross-learning contextual bandits with graphical feedback, where playing an arm reveals the losses of its out-neighbors in every context. A central open question was whether, under i.i.d. contexts and a fixed strongly observable feedback graph with independence number $α$, one can remove every polynomial dependence on the number of contexts while attaining the classical graphical-bandit rate $\widetilde O(\sqrt{αT})$. The question was open even for stochastic losses and graphs in which every arm has a self-loop. We answer it affirmatively under the stronger model of oblivious adversarial losses and for all strongly observable graphs, including those with arms without self-loops. The key obstruction is that a frequently played no-self-loop arm can nevertheless have a vanishing observation probability. Our algorithm isolates one such arm per epoch, uses a pessimistic correction to cancel its first-order estimation drift, and shifts the losses in the FTRL analysis to control the resulting quadratic term. It achieves expected regret $\widetilde O(\sqrt{αT})$. Controlled synthetic experiments show the benefit of combining graph feedback with cross-learning and exhibit the predicted scaling in both $T$ and $α$. The main theorem is formalized in Lean in an end-to-end development exceeding 100,000 lines of Lean code. The formalization and experiment artifacts are available in the GitHub repository: https://github.com/RuiyuanHuang/graphical-cross-learning-review-artifact.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。