On the Impact of Side-Information in Bandit Learning: More is Not Always Merrier

More data is commonly assumed to improve learning performance. We show that this intuition can fail in sequential decision-making. Motivated by multi-agent collaborative learning, we study stochastic bandits with exogenous side information, and ask if free and unbiased reward samples are guaranteed to reduce regret. We introduce a formal notion of non-degradation under side information and demonstrate that the widely used UCB algorithm violates this property: there exist benign side-information designs under which UCB incurs strictly higher regret than when run without side information. We contrast this behavior with Thompson Sampling and Explore-Then-Commit, which benefit from the same information. Constructively, we further propose a meta-algorithm that enforces non-degradation for a broad class of bandit algorithms. Finally, experiments in recommender systems scenarios show that data sharing among different groups of users under UCB can yield diminishing and even negative returns for individual groups.