Search papers, labs, and topics across Lattice.
This paper analyzes the problem of fixed-budget best arm identification in grouped bandits with feasibility constraints, where arms are feasible only if all their attributes' means exceed a threshold. A lower bound on the error probability is derived, and a novel algorithm, Feasibility Constrained Successive Rejects (FCSR), is proposed to identify the best feasible arm. FCSR is proven to achieve optimal dependence on problem parameters in the exponent and demonstrates superior empirical performance compared to baseline methods.
Finding the best option when you need to balance multiple requirements and a limited budget is now provably more efficient, thanks to a new algorithm that guarantees feasibility.
We study fixed budget constrained best-arm identification in grouped bandits, where each arm consists of multiple independent attributes with stochastic rewards. An arm is considered feasible only if all its attributes' means are above a given threshold. The aim is to find the feasible arm with the largest overall mean. We first derive a lower bound on the error probability for any algorithm on this setting. We then propose Feasibility Constrained Successive Rejects (FCSR), a novel algorithm that identifies the best arm while ensuring feasibility. We show it attains optimal dependence on problem parameters up to constant factors in the exponent. Empirically, FCSR outperforms natural baselines while preserving feasibility guarantees.
