用贝叶斯方法改进在线学习，应对无限专家场景下的对抗性挑战
Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spaces
- 将先验设为对手未来动作空间，而非专家空间，重构学习机制
- 在有限专家情况下达到最优后悔率，在无限动作空间中实现√(Td log d)的收敛速度
- 适合研究在线学习与贝叶斯优化交叉问题的研究者，尤其关注对抗性环境
我们提出一种针对全反馈在线学习（即专家建议预测）的贝叶斯型汤普森采样方法，其中学习者的先验定义在对手未来动作的空间上，而非专家空间。我们证明后悔可分解为先验预期后悔与一种称为超额后悔的先验鲁棒性项之和。在经典有限专家设置下，该方法恢复了最优后悔率。作为向具有潜在不可数无穷多专家场景的实用在线学习迈出的第一步，我们证明：在d维单位立方体上使用贝叶斯优化中常用的高斯过程先验进行汤普森采样，面对β-有界、λ-利普希茨对手时，其后悔率为𝒪(β√(T d log(1 + √d λ/β)))。
原文摘要 · Abstract (English)
We develop a form Thompson sampling for online learning under full feedback - also known as prediction with expert advice - where the learner's prior is defined over the space of an adversary's future actions, rather than the space of experts. We show regret decomposes into regret the learner expected a priori, plus a prior-robustness-type term we call excess regret. In the classical finite-expert setting, this recovers optimal rates. As an initial step towards practical online learning in settings with a potentially-uncountably-infinite number of experts, we show that Thompson sampling over the $d$-dimensional unit cube, using a certain Gaussian process prior widely-used in the Bayesian optimization literature, has a $\mathcal{O}\Big(β\sqrt{Td\log(1+\sqrt{d}\fracλβ)}\Big)$ rate against a $β$-bounded $λ$-Lipschitz adversary.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。