Nonstationary Multi-Armed Bandits with Heterogeneous Arm Classes

In real-world applications such as online recommendation, nonstationarity is rarely uniform: trending items fluctuate rapidly, while the broader catalog remains stable. Existing nonstationary bandit algorithms ignore this structure, incurring regret that scales with the global product of total arms and total switches. To address this, we formulate nonstationary multi-armed bandits with heterogeneous arm classes, where $K$ arms are partitioned into $M$ known classes of sizes $K_m$ with individual change budgets $L_m$. We design an adaptive algorithm requiring no prior knowledge of these budgets that achieves expected dynamic regret of order $\sqrt{MT{\sum }_m(L_m+1)K_m}$, tightly pairing each class's volatility with only its own size. Finally, we establish complementary lower bounds showing that this rate is optimal up to logarithmic factors for fixed $M$, and that the $\sqrt{M}$ class-search overhead is fundamentally unavoidable in general.