# Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget

arXiv: https://arxiv.org/abs/2211.14768 · HTML: https://mlsanity.com/paper/2211.14768/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 25 references that are in the map.
- First posted on arXiv 27 Nov 2022.

## Builds on (most cited first, 13 of 13)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Risk-Averse Multi-Armed Bandit Problems under Mean-Variance Measure](https://mlsanity.com/paper/1604.05257/) (2016)
- [Distribution oblivious, risk-aware algorithms for multi-armed bandits with unbounded rewards](https://mlsanity.com/paper/1906.00569/) (2019)
- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [Multi-objective Contextual Multi-armed Bandit with a Dominant Objective](https://mlsanity.com/paper/1708.05655/) (2017)
- [Concentration bounds for empirical conditional value-at-risk: The unbounded case](https://mlsanity.com/paper/1808.01739/) (2018)
- [Risk-Constrained Thompson Sampling for CVaR Bandits](https://mlsanity.com/paper/2011.08046/) (2020)
- [Constrained regret minimization for multi-criterion multi-armed bandits](https://mlsanity.com/paper/2006.09649/) (2020)
- [An Asymptotically Optimal Strategy for Constrained Multi-armed Bandit Problems](https://mlsanity.com/paper/1805.01237/) (2018)

## Built on by (most cited first, 9 of 9)

- [Bandit Pareto Set Identification: the Fixed Budget Setting](https://mlsanity.com/paper/2311.03992/) (2023)
- [Pure Exploration in Bandits with Linear Constraints](https://mlsanity.com/paper/2306.12774/) (2023)
- [Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget](https://mlsanity.com/paper/2405.15090/) (2024)
- [Bandit Pareto Set Identification in a Multi-Output Linear Model](https://mlsanity.com/paper/2507.04255/) (2025)
- [Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits](https://mlsanity.com/paper/2605.14553/) (2026)
- [Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget](https://mlsanity.com/paper/2506.02386/) (2025)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Fixed-Budget Constrained Best Arm Identification in Grouped Bandits](https://mlsanity.com/paper/2603.04007/) (2026)
- [Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints](https://mlsanity.com/paper/2410.18844/) (2024)

## Abstract (arXiv)

We consider a constrained, pure exploration, stochastic multi-armed bandit formulation under a fixed budget. Each arm is associated with an unknown, possibly multi-dimensional distribution and is described by multiple attributes that are a function of this distribution. The aim is to optimize a particular attribute subject to user-defined constraints on the other attributes. This framework models applications such as financial portfolio optimization, where it is natural to perform risk-constrained maximization of mean return. We assume that the attributes can be estimated using samples from the arms' distributions and that these estimators satisfy suitable concentration inequalities. We propose an algorithm called textscConstrained-SR based on the Successive Rejects framework, which recommends an optimal arm and flags the instance as being feasible or infeasible. A key feature of this algorithm is that it is designed on the basis of an information theoretic lower bound for two-armed instances. We characterize an instance-dependent upper bound on the probability of error under textscConstrained-SR, that decays exponentially with respect to the budget. We further show that the associated decay rate is nearly optimal relative to an information theoretic lower bound in certain special cases.