提出首个在一般高斯带模型中渐近最优的算法，利用额外信息提升决策效率。
Asymptotically-Optimal Gaussian Bandits with Side Observations
- 基于线性规划构建下界，量化可靠估计每支臂差距所需的最小代价
- 设计新算法，在任意已知侧信信息矩阵下实现渐近最优的累积损失
- 适用于有结构反馈或信息共享的强化学习场景，如多臂博弈、推荐系统
我们研究了带有通用侧信息的高斯带模型，该设定由Wu、Szepesvári和György首次提出。在此框架中，选择某一支臂会根据预先已知的侧信息矩阵，揭示其他臂的信息：矩阵中每个元素表示‘行’臂对‘列’臂信息的可信度。在高斯噪声情况下，该模型涵盖了标准带、全反馈以及图结构反馈等多种情形。本文首先构建了一个基于线性规划的渐近实例相关下界，用于刻画可靠估计每支臂次优差距所需的最小后悔值。这一下界启发了我们的核心贡献：首个在该通用设定下渐近最优的算法。
原文摘要 · Abstract (English)
We study the problem of Gaussian bandits with general side information, as first introduced by Wu, Szepesvari, and Gyorgy. In this setting, the play of an arm reveals information about other arms, according to an arbitrary a priori known side information matrix: each element of this matrix encodes the fidelity of the information that the ``row'' arm reveals about the ``column'' arm. In the case of Gaussian noise, this model subsumes standard bandits, full-feedback, and graph-structured feedback as special cases. In this work, we first construct an LP-based asymptotic instance-dependent lower bound on the regret. The LP optimizes the cost (regret) required to reliably estimate the suboptimality gap of each arm. This LP lower bound motivates our main contribution: the first known asymptotically optimal algorithm for this general setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。