Frequency-Agnostic Online Clustering of Bandits via Local Certification

For a linear bandit problem, in each sequential decision round, an agent picks an action vector and receives a stochastic reward whose expectation is the inner product of the action vector and an unknown preference vector. Online clustering of linear bandits improves sample efficiency by grouping agents with common preferences into clusters and pooling their observations. However, prior analyses often tie the benefits of collaboration to the identification of the full cluster structure, so rarely observed agents can delay these benefits even for agents whose preferences are already estimated accurately. To address this limitation, we introduce Local Certification for Clustering of Bandits (LC-CLUB), a frequency-agnostic collaboration framework that enables certified sharing before global cluster identification and requires no knowledge of arrival frequencies. Each agent first learns from its own observations and, once its estimate is accurate enough to be certified, begins sharing with certified agents in the same cluster. Our regret analysis separates each agent's pre-certification interactions from its subsequent cluster-level learning, so a rarely observed agent contributes only its own few interactions to the clustering term. With this new algorithm design and analysis, LC-CLUB eliminates the uniform-arrival assumption imposed in prior analyses, has no inverse dependence on the minimum agent-arrival probability, and requires no within-cluster frequency alignment, substantially broadening its applicability to heterogeneous-arrival settings with highly unequal agent arrival rates. It also removes an explicit factor of the linear-bandit dimension $d$ from the coefficient of $\log T$ in the clustering term, leaving a horizon-independent remainder. We further show that, under Gaussian-perturbed adversarial contexts, predictable convex action-selection scores, including LinUCB, accumulate information in every direction at a linear rate with high probability, so local certification needs no separate uniform-exploration phase. Experimentally, LC-CLUB-L reduces cumulative regret by 12.8% on average and up to 38% relative to the strongest baseline.