利用动作相似性降低在线学习的后悔值，突破传统方法局限。
Leveraging Similarities in Multi-Armed Bandits
- 用树结构建模动作相似性，将相关动作分组以提升学习效率。
- 在双点反馈下，二维李普希茨问题可实现√T后悔率，优于传统方法。
- 适用于多点反馈到最小双点反馈的统一算法，适合有结构化动作的场景。
在许多在线学习和贝叶斯优化问题中，动作之间存在固有的相似性——例如共享潜在特征、标签或层级结构。本文研究具有相似性结构的动作集上的在线学习，其动作关系由一棵以动作为叶子节点的根树编码，层级表示动作间的相似程度。损失序列满足树兼容性：相似动作的损失被约束为接近。我们证明了一个不可能性结果：通常的一点反馈无法一般性地利用范围或树诱导的相似性，即使在强相似性约束下亦然。随后，我们提出一套统一算法，适应从半反馈到多点反馈（包括最小两点反馈）的多种丰富反馈模型。这些算法表现出‘最好两者兼顾’的性能保证，并通过用相似性感知的有效动作数 $K_{\mathrm{eff}}$ 替代动作总数 $K$，在后悔界中显式利用动作相似性。作为应用，我们证明在两点反馈下，当 $d \leq 2$ 时，李普希茨贝叶斯优化可达到 $\sqrt{T}$ 的后悔率。
原文摘要 · Abstract (English)
In many online learning and bandit problems, the actions we consider possess inherent similarities--for instance because they share latent traits, tags, or hierarchical structure. We study online learning with a similarity-structured action set, encoded by a rooted tree whose leaves are the actions and whose levels quantify how closely two actions are related. The loss sequence is assumed tree-compatible: losses of similar actions are constrained to be close. We establish an impossibility result showing that usual one-point bandit feedback cannot, in general, leverage range or tree-induced similarity, even under very strong similarity constraints. We then provide a unified set of algorithms which adapt to a wide range of richer feedback models, from semi-bandit feedback down to multi-point bandit protocols, including the minimal two-point feedback setting. We show these algorithms exhibit best-of-both-worlds guarantees and provably exploit action similarities by replacing the number of actions $K$ by a similarity-aware effective number of actions $K_{\mathrm{eff}}$ in the regret bounds. As an application, we show that under two-point feedback, it is possible to achieve $\sqrt{T}$ regret in Lipschitz bandits when $d \leq 2$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。