Scalable Exploration via Ensemble++

Understand

Thompson Sampling is a principled method for balancing exploration and exploitation, but its real-world adoption faces computational challenges in large-scale or non-conjugate settings.

• While ensemble-based approaches offer partial remedies, they typically require prohibitively large ensemble sizes.
• We propose Ensemble++, a scalable exploration framework using a novel shared-factor ensemble architecture with random linear combinations.
• For linear bandits, we provide theoretical guarantees showing that Ensemble++ achieves regret comparable to exact Thompson Sampling with only $\Theta(d \log T)$ ensemble sizes--significantly outperforming prior methods.