  We consider a K-armed bandit problem in general graphs where agents are
arbitrarily connected and each of them has limited memorizing capabilities and
communication bandwidth. The goal is to let each of the agents eventually learn
the best arm. It is assumed in these studies that the communication graph
should be complete or well-structured, whereas such an assumption is not always
valid in practice. Furthermore, limited memorization and communication
bandwidth also restrict the collaborations of the agents, since the agents
memorize and communicate very few experiences. Additionally, an agent may be
corrupted to share falsified experiences to its peers, while the resource limit
in terms of memorization and communication may considerably restrict the
reliability of the learning process. To address the above issues, we propose a
three-staged collaborative learning algorithm. In each step, the agents share
their latest experiences with each other through light-weight random walks in a
general communication graph, and then make decisions on which arms to pull
according to the recommendations received from their peers. The agents finally
update their adoptions (i.e., preferences to the arms) based on the reward
obtained by pulling the arms. Our theoretical analysis shows that, when there
are a sufficient number of agents participating in the collaborative learning
process, all the agents eventually learn the best arm with high probability,
even with limited memorizing capabilities and light-weight communications. We
also reveal in our theoretical analysis the upper bound on the number of
corrupted agents our algorithm can tolerate. The efficacy of our proposed
three-staged collaborative learning algorithm is finally verified by extensive
experiments on both synthetic and real datasets.
