CluE: Cluster, Sample & Eliminate - Bayesian Block Elimination for Pure Exploration with Non-binary Rewards and Limited Budget

We introduce CluE (Cluster, Sample & Eliminate), a novel approach tailored for pure-exploration bandit problems with limited budget. Several problems in machine learning, including dynamic pricing and dynamic model pruning are conceptualized as pure-exploration dynamic assignment problems constrained by budgets. Given a high-dimensional action space and exploration budget, CluE operates by first discretizing the action space into a manageable set of discrete actions and then clustering these actions. The algorithm proceeds in phases, selectively sampling from the most promising cluster and refining choices to the optimal action within that cluster. Suboptimal clusters are eliminated at the end of each phase based on confidence bounds estimates. We have conducted extensive testing in federated learning and logistics, demonstrating that CluE substantially lowers the misidentification probability compared to leading elimination-based algorithms in pure-exploration settings.