Online Learning with Noisy Side Observations
Online Learning with Noisy Side Observations
复制标题
在线学习与嘈杂的侧面观察
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Michal Valko
中科院分区：
文献类型：
--
作者：
Tomás Kocák;Gergely Neu;Michal Valko
我们提出了一个新的在线学习问题的部分可观测性模型，其中学习者除了自身的损失外，还观察到关于其他行为的一些噪声反馈，这取决于问题的底层结构。我们用一个加权有向图来表示这种结构，其中边的权重与连接节点共享的反馈的质量有关。我们的主要贡献是提供了一个高效的算法，保证在T轮之后的遗憾为O(√α*T)，其中α*是一种新的图性质，我们称之为有效独立数。我们的算法是完全无参数的，不需要α*的知识(甚至不需要估计)。对于二元边权的特殊情况，我们的设置简化为Mannor&Shamir(2011)和Alon等人的部分可观测性模型。(2013)，并且我们的算法恢复了接近最优的后悔界限。
We propose a new partial-observability model for online learning problems where the learner, besides its own loss, also observes some noisy feedback about the other actions, depending on the underlying structure of the problem. We represent this structure by a weighted directed graph, where the edge weights are related to the quality of the feedback shared by the connected nodes. Our main contribution is an efficient algorithm that guarantees a regret of O(√ α * T) after T rounds, where α * is a novel graph property that we call the effective independence number. Our algorithm is completely parameter-free and does not require knowledge (or even estimation) of α *. For the special case of binary edge weights, our setting reduces to the partial-observability models of Mannor & Shamir (2011) and Alon et al. (2013) and our algorithm recovers the near-optimal regret bounds.