Online learning with Erdos-Renyi side-observation graphs
Online learning with Erdos-Renyi side-observation graphs
复制标题
鄂尔多斯-仁义旁观图在线学习
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Michal Valko
中科院分区：
文献类型：
--
作者：
Tomás Kocák;Gergely Neu;Michal Valko
我们考虑对抗性的多臂强盗问题，学习者被允许观察损失的一些武器旁边的手臂，它实际上选择。我们研究的情况下，所有非选择的武器揭示他们的损失与未知的概率RT，独立于彼此和学习者的行动。此外，我们允许rt在每一轮t中发生变化，这排除了通过高度集中的样本平均值估计rt的可能性。我们提出了一个算法，它的运作的假设下，RT是足够大，以保证至少有一个方面的观察具有高概率。我们证明了在N个臂的强盗问题中，经过T轮后，我们算法的期望后悔度为O（n ≤ Tt-1（1/rt）logN），其中对所有t，rt ≥ logT/（2N - 2）.我们所有的界限都在任何算法的最佳可实现性能的对数因子之内，甚至允许知道rt的精确值。
We consider adversarial multi-armed bandit problems where the learner is allowed to observe losses of a number of arms beside the arm that it actually chose. We study the case where all non-chosen arms reveal their loss with an unknown probability rt, independently of each other and the action of the learner. Moreover, we allow rt to change in every round t, which rules out the possibility of estimating rt by a well-concentrated sample average. We propose an algorithm which operates under the assumption that rt is large enough to warrant at least one side observation with high probability. We show that after T rounds in a bandit problem with N arms, the expected regret of our algorithm is of order O(√ΣTt-1 (1/rt) log N), given that rt ≥ log T/(2N - 2) for all t. All our bounds are within logarithmic factors of the best achievable performance of any algorithm that is even allowed to know exact values of rt.