  We define and analyze a multi-agent multi-armed bandit problem in which
decision-making agents can observe the choices and rewards of their neighbors.
Neighbors are defined by a network graph with heterogeneous and stochastic
interconnections. These interactions are determined by the sociability of each
agent, which corresponds to the probability that the agent observes its
neighbors. We design an algorithm for each agent to maximize its own expected
cumulative reward and prove performance bounds that depend on the sociability
of the agents and the network structure. We use the bounds to predict the rank
ordering of agents according to their performance and verify the accuracy
analytically and computationally.
