Fixed-Budget Constrained Best Arm Identification in Grouped Bandits

• URL: http://arxiv.org/abs/2603.04007v1
• Date: Wed, 04 Mar 2026 12:49:56 GMT
• Title: Fixed-Budget Constrained Best Arm Identification in Grouped Bandits
• Authors: Raunak Mukherjee, Sharayu Moharir,
• Abstract summary: We study fixed budget constrained best-arm identification in grouped bandits, where each arm consists of multiple independent attributes with rewards.<n>We propose Feasibility Constrained Successive Rejects (FCSR), a novel algorithm that identifies the best arm while ensuring feasibility.
• Score: 1.360738859820932
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  We consider a multi-armed bandit setting in which each arm yields an $M$-dimensional vector reward upon selection.<n>The end goal is to identify the best arm of em every objective in the shortest (expected) time subject to an upper bound on the probability of error.<n>We propose an algorithm that uses the novel idea of em surrogate proportions to sample the arms at each time step, eliminating the need to solve the max-min optimisation problem at each step.
  arXiv  Detail & Related papers  (2025-01-23T12:28:09Z)
• Constrained Best Arm Identification in Grouped Bandits [3.387374559368306]
  We study a grouped bandit setting where each arm comprises multiple independent sub-arms referred to as attributes.<n>We impose the constraint that for an arm to be deemed feasible, the mean reward of all its attributes should exceed a specified threshold.<n>The goal is to find the arm with the highest mean reward averaged across attributes among the set of feasible arms in the fixed confidence setting.
  arXiv  Detail & Related papers  (2024-12-11T02:19:19Z)
• Best-Arm Identification in Unimodal Bandits [24.001611176749158]
  We study the fixed-confidence best-arm identification problem in unimodal bandits.<n>We derive two lower on the stopping time of any bounds.<n>We show that a linear dependence on the number of arms is unavoidable in the confidence-independent cost.
  arXiv  Detail & Related papers  (2024-11-04T09:05:11Z)
• Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
  We introduce the constrained best mixed arm identification (CBMAI) problem with a fixed budget. The goal is to find the best mixed arm that maximizes the expected reward subject to constraints on the expected costs with a given learning budget $N$. We provide a theoretical upper bound on the mis-identification (of the the support of the best mixed arm) probability and show that it decays exponentially in the budget $N$.
  arXiv  Detail & Related papers  (2024-05-23T22:35:11Z)
• Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
  We study best arm identification in a restless multi-armed bandit setting with finitely many arms. The discrete-time data generated by each arm forms a homogeneous Markov chain taking values in a common, finite state space. It is demonstrated that tracking the long-term behavior of a certain Markov decision process and its state-action visitation proportions are the key ingredients in analyzing the converse and achievability bounds.
  arXiv  Detail & Related papers  (2023-10-20T10:04:05Z)
• Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget [4.226118870861363]
  We consider a constrained, pure exploration, multi-armed bandit formulation under a fixed budget. We propose an algorithm called textscConstrained-SR based on the Successive Rejects framework. We show that the associated decay rate is nearly optimal relative to an information theoretic lower bound in certain special cases.
  arXiv  Detail & Related papers  (2022-11-27T08:58:16Z)
• Semiparametric Best Arm Identification with Contextual Information [10.915684166086026]
  We study best-arm identification with a fixed budget and contextual information in bandit problems. We develop the "Contextual RS-AIPW strategy," which consists of the random sampling rule tracking a target allocation ratio and the recommendation rule. Our proposed Contextual RS-AIPW strategy is optimal because the upper bound for the probability of misidentification matches the semi lower bound when the budget goes to infinity.
  arXiv  Detail & Related papers  (2022-09-15T14:38:47Z)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  We study the problem of identifying the best arm in a multi-armed bandit environment. A decision entity wishes to find the index of the best arm as quickly as possible, subject to an upper bound error probability. We show that this policy achieves an upper bound that depends on $R$ and is monotonically non-increasing as $Rtoinfty$.
  arXiv  Detail & Related papers  (2022-03-29T04:58:04Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-14T21:49:58Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  We devise a simple algorithm whose sampling complexity matches known instance-specific lower bounds. Unlike existing best-arm identification strategies, our algorithm uses a stopping rule that does not depend on the number of arms.
  arXiv  Detail & Related papers  (2020-06-29T14:25:51Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  We introduce a theory for multi-armed bandits where the values are the modes of the reward distributions instead of the mean. We show in simulations that our algorithms are robust to perturbation of the arms by adversarial noise sequences.
  arXiv  Detail & Related papers  (2020-03-05T21:29:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.