We consider a collaborative online learning paradigm, wherein a group of agents connected through a social network are engaged in learning a Multi-Armed Bandit problem. Each time an agent takes an action, the corresponding reward is instantaneously observed by the agent, as well as its neighbours in the social network. We perform a regret analysis of various policies in this collaborative learning setting. A key finding of this paper is that appropriate network extensions of widely-studied single agent learning policies do not perform well in terms of regret. In particular, we identify a class of non-altruistic and individually consistent policies, which could suffer a large regret. We also show that the regret performance can be substantially improved by exploiting the network structure. Specifically, we consider a star network, which is a common motif in hierarchical social networks, and show that the hub agent can be used as an information sink, to aid the learning rates of the entire network. We also present numerical experiments to corroborate our analytical results.