In this paper we propose a novel framework for decentralized, online learning by many learners. At each moment of time, an instance characterized by a certain context may arrive to each learner; based on the context, the learner can select one of its own actions (which gives a reward and provides information) or request assistance from another learner. In the latter case, the requester pays a cost and receives the reward but the provider learns the information. In our framework, learners are modeled as cooperative contextual bandits. Each learner seeks to maximize its own expected reward, which involves trading off the reward received from its own actions, the information learned from its own actions, the reward received from the actions requested of others and the cost paid for these actions - taking into account what it has learned about the value of assistance from each specific other learner. We develop distributed online learning algorithms and provide analytic estimates to compare the efficiency of these with algorithms with the complete knowledge benchmark (in which the expected reward of every choice in every context is known by every learner). Our estimates show that regret - the loss incurred by the algorithm - is sublinear in time. Our theoretical framework can be used in many practical applications including Big Data mining, event detection in surveillance sensor networks and distributed online recommendation systems.

本文提出了一种新的分布式在线学习框架，将学习者建模为合作的情境赌博机，分析了分布式在线学习算法和完全知识基准的效率，研究表明后者在时间上失误是亚线性的，该理论框架可用于许多实际应用中，包括大数据挖掘、监视传感器网络事件检测和分布式在线推荐系统。

基于合作上下文臂银行算法的分布式在线学习