If the additional arms appear late, my intuition is to use one algorithm for the old parts and one for the new arms, and a weighting factor to decide which model to use. This procedure can be generalized for generational partitions. For example you group the old arms into group A and the new arms in group B, and a bandit with two arms to decide which group to use, then inside each group you apply your favorite bandit algorithm, that is not a divide and conquer algorithm but has something in common. This is a hierarchical model.