We consider an adversarial online learning setting where a decision maker can choose an action in every stage of the game. In addition to observing the reward of the chosen action, the decision maker gets side observations on the reward he would have obtained had he chosen some of the other actions. The observation structure is encoded as a graph, where node $i$ is linked to node $j$ if sampling $i$ provides information on the reward of $j$. This setting naturally interpolates between the well-known "experts" setting, where the decision maker can view all rewards, and the multi-armed bandits setting, where the decision maker can only view the reward of the chosen action. We develop practical algorithms with provable regret guarantees, as well as partially-matching lower bounds. The regret depends on non-trivial graph theoretic properties of the information feedback structure, and reveals an interesting trade-off between regret optimality and computational efficiency.

本文探讨了一种对抗性在线学习情境，其中决策者可以在每个阶段选择一个行动，并观察到给定行动的奖励，同时还能获取有关选择其他行动所获得的奖励的信息。研究者们开发出具有可证明的后悔保证的实用算法，这些算法依赖于非平凡的图论信息反馈结构特性。

从强盗到专家：浅谈旁观价值