Open problem: fixed-budget best arm identification complexity.
problem Understanding the complexity of identifying the best arm in a fixed budget setting.
method Analyzing existing results and conjectures in the fixed-confidence setting.
result Open questions remain about the fixed-budget setting.
New findings on complexity limits in fixed budget bandit identification.
problem Determining the best possible error rate for fixed budget bandit identification.
method Analyzing the best non-adaptive sampling procedures and showing the existence of complexities.
result No fixed complexity for certain bandit identification tasks.
Algorithm identifies best arm with prior info in structured bandits.
problem Bayesian fixed-budget best-arm identification in structured bandits.
method Prior-dependent allocations based on structure and prior information.
result Improved theoretical bounds and robust performance across diverse models.
UCB exploration improves best arm identification in fixed-budget settings.
problem Best arm identification in fixed-budget scenarios.
method Adaptive allocations based on upper confidence bounds (UCBs) with prior information learning.
result Empirically and theoretically efficient for Bayesian BAI problem with improved performance.
New algorithms for model selection in linear bandits adapt to instance complexity.
problem Adapting to the instance-dependent complexity of the true model in linear bandits.
method Design of algorithms in fixed confidence and fixed budget settings, leveraging experimental design and selection-validation procedures.
result Near instance optimal guarantees for model selection in linear bandits.
Bayesian algorithm improves best-arm identification within fixed budget.
problem Maximizing probability of identifying optimal arm within fixed budget.
method Proposes Bayesian elimination algorithm and derives upper bound on misidentification probability.
result Upper bound on misidentification probability reflects prior quality and matches lower bound.
New algorithm identifies optimal subtrees in fixed-budget tree search.
problem Identifying optimal subtrees in fixed-budget Monte Carlo Tree Search.
method ε-agnostic algorithm for max-min action identification.
result Misidentification probability decays exponentially with sample size.
New research shows fixed-budget best-arm identification cannot match static oracle performance.
problem Fixed-budget best-arm identification's performance limitations.
method Analysis of various adaptive and static algorithms for best-arm identification.
result For any algorithm, there exists at least one instance where the error decay rate is at most \((1 + \frac{\log(K)}{8})^{-1}\) times that of the static oracle.
New policy minimizes error in finding best arm with privacy constraints.
problem Best arm identification with differential privacy constraints.
method Maximum absolute determinants principle for ε-DP policy. result Error probability decays exponentially in T with matching exponents. APGAI identifies good arms anytime with fixed budget.
problem Identifying a good arm with a fixed sampling budget.
method An anytime algorithm for good arm identification in stochastic bandits.
result APGAI achieves efficient detection of good arms with upper bounds on probability of error and sampling complexity.
This paper proposes a new AED framework for multi-metric experiments with fixed budget.
problem Statistical power challenges in testing multiple metrics simultaneously.
method Two-phase structure: adaptive exploration followed by validation. SHRVar algorithm with relative-variance-based sampling.
result Achieves provable error probability that decreases exponentially.
LinearAPT optimizes decision-making under resource constraints for a linear threshold problem.
problem Optimizing sequential decisions with a linear threshold under resource limitations.
method LinearAPT, an adaptive algorithm for fixed-budget TLB problem.
result LinearAPT achieves theoretical upper bounds and robust performance on various datasets.
The paper develops a theory for identifying the best arm in non-parametric multi-armed bandits with a fixed budget.
problem Identifying the best arm in non-parametric multi-armed bandits with a limited number of trials.
method The paper proposes upper and lower bounds on the average log-probability of misidentification using information-theoretic quantities and a refined analysis of the successive-rejects strategy.
result The paper provides new upper and lower bounds on the average log-probability of misidentification, which generalize existing bounds.
A/B testing refers to the task of determining the best option among two alternatives that yield random outcomes. We provide distribution-dependent lower bounds for the performance of A/B testing that improve over the results currently available both in the fixed-confidence (or delta-PAC) and fixed-budget settings. When…
We consider the problem of \textit{best arm identification} with a \textit{fixed budget T}, in the K-armed stochastic bandit setting, with arms distribution defined on [0,1]. We prove that any bandit strategy, for at least one bandit problem characterized by a complexity H, will misidentify the best arm with pr…
Optimal strategy identified for minimizing regret in fixed-budget best arm selection.
problem Minimizing expected simple regret in fixed-budget best arm selection.
method Two-Stage (TS)-Hirano-Imbens-Ridder (HIR) strategy using HIR estimator.
result TS-HIR strategy is asymptotically minimax optimal.
Optimal strategy found for identifying best arm in bandits with small gap.
problem Best arm identification in two-armed bandits with a fixed budget and small gap.
method Neyman allocation rule augmented with inverse probability weighting.
result Proposed strategy is asymptotically optimal when gap is small.
ReD improves LLM inference efficiency at fixed budget, reducing attempts and cost.
problem Improving LLM inference efficiency at a fixed budget.
method Reset-and-Discard (ReD) query method.
result ReD increases coverage@cost for a given budget, reducing attempts and cost.
Paper shows FB and FC are equally hard up to logarithmic factors.
problem Comparing fixed budget and fixed confidence approaches in best-arm identification.
method Proposes FC2FB, a meta algorithm converting FC to FB.
result FC sample complexity is an upper bound for FB sample complexity up to logarithmic factors.
New algorithms identify Pareto optimal sets in multi-objective bandit problems.
problem Identifying Pareto optimal sets in multi-objective bandit problems.
method Empirical Gap Elimination (EGE) algorithms combining hardness estimation and elimination schemes.
result Two EGE algorithms have exponentially decaying error probabilities with budget.
A two-phase algorithm identifies the best arm in sparse linear bandits with fixed budget.
problem Best arm identification in sparse linear bandits with limited budget.
method Lasso and Optimal-Design (Lasso-OD) based linear best-arm identification.
result Lasso-OD achieves significant performance improvement for sparse and high-dimensional linear bandits.
New algorithms improve best-arm identification with varying rewards.
problem Identifying the best arm with varying reward variances in fixed budget.
method Proposed two algorithms: SHVar for known variances, SHAdaVar for unknown variances; uses non-uniform budget allocation.
result Bounding misidentification probabilities for both algorithms.
Optimizes identifying the best arm with fixed samples.
problem Finding the arm with the highest mean in a fixed number of samples.
method Characterizes minimax optimal rates and introduces algorithms to achieve them.
result Characterizes and introduces algorithms for optimal best arm identification.
New algorithm finds best feasible arm in grouped bandits.
problem Finding the best arm with all attributes above a threshold.
method Feasibility Constrained Successive Rejects (FCSR) algorithm.
result FCSR identifies the best feasible arm with optimal dependence on problem parameters.
The stochastic multi-armed bandit model is a simple abstraction that has proven useful in many different contexts in statistics and machine learning. Whereas the achievable limit in terms of regret minimization is now well known, our aim is to contribute to a better understanding of the performance in terms of identify…
Improved adaptive algorithms for identifying the best arm in MABs with fixed budget.
problem Identifying the best arm in stochastic Multi-Armed Bandits with a fixed sampling budget.
method Established a connection between Large Deviation Principles and adaptive algorithms, improving error probability bounds and devising new algorithms.
result The \sred algorithm outperforms existing algorithms in identifying the best arm.
New method balances performance and cost in identifying best arm.
problem Identifying the best arm in multi-armed bandit models.
method Minimizes a risk functional that balances performance and cost.
result Proposes DBCARE algorithm that matches theoretical lower bounds.
Study identifies change points in piecewise constant reward functions with fixed exploration budget.
problem Locating abrupt changes in piecewise constant reward functions under bandit feedback.
method Fixed exploration budget, piecewise constant bandit problem, lower bounds, near optimal algorithms.
result Established lower bounds and near matching upper bounds for both small and large budgets.
GNA optimally identifies the best arm with small gaps.
problem Best arm identification in fixed-budget settings.
method Generalized Neyman Allocation (GNA) for asymptotically locally minimax optimal BAI.
result GNA's worst-case bounds match the lower and upper bounds in the small-gap regime.
EB-TCε identifies the best arm with ε confidence in stochastic bandits.
problem Identifying the best arm in stochastic bandits with a fixed level of confidence.
method EB-TCε is a novel sampling rule for ε-best arm identification in stochastic bandits.
result EB-TCε is the first anytime algorithm for fixed confidence or fixed budget identification.
New algorithm identifies best arm with optimal budget usage.
problem Identifying the arm with the highest mean reward from multiple options.
method Proposes Almost Tracking, a closed-form algorithm for anytime best arm identification.
result Proven to be rate-optimal and outperforms existing algorithms.
Bayes optimal algorithm under certain conditions doesn't achieve exponential simple regret.
problem Best arm identification with normal rewards over time.
method Fixed-budget best arm identification problem with rewards from normal distributions. Evaluates performance via simple regret.
result Bayes optimal algorithm does not yield exponential decrease in simple regret.
Study optimizes best-arm identification with minimax and Bayes strategies.
problem Efficiently identifying the best arm in fixed-budget scenarios.
method Adaptive procedure with two stages: pilot phase and minimax game.
result Single strategy is asymptotically minimax and Bayes optimal.
Optimal ability estimation in adaptive testing with binary responses.
problem Estimating a continuous ability parameter from sequential binary responses.
method Adaptive selection of questions to maximize Fisher information, updating estimate using method-of-moments, and deciding accuracy with a test statistic.
result Fisher-tracking strategy achieves optimal performance in fixed-confidence and fixed-budget regimes.
The paper develops algorithms to minimize misallocation and identify the arm with the highest variance.
problem Minimizing misallocation and identifying the arm with the highest variance from a set of arms.
method Developed novel online algorithms UCB-VV for misallocation minimization and SHVV for fixed budget best arm identification.
result The algorithms achieve optimal performance in terms of misallocation and error probability.
The paper offers efficient algorithms for combinatorial and linear bandits using empirical process theory.
problem Optimal algorithms for combinatorial and linear bandits with practical sample complexity.
method Empirical process theory, Gaussian-width, minimizing experimental design objective.
result Sample complexity matches lower bounds, especially for combinatorial classes.
Estimating the largest community in a mixed population via sequential sampling.
problem Identifying the largest community in a mixed population with limited sampling.
method Sequential, random sampling of individuals across multiple boxes, optimizing sampling strategy and decision rule.
result Proposed algorithms achieve optimal error probability decay rates under fixed budget constraints.
Optimal algorithm for identifying best-arm with minimal regret.
problem Identifying the best arm in two treatments with limited budget.
method Neyman allocation based on outcome standard deviations.
result Neyman allocation is minimax optimal for simple regret.
We consider the thresholding bandit problem, whose goal is to find arms of mean rewards above a given threshold θ, with a fixed budget of T trials. We introduce LSA, a new, simple and anytime algorithm that aims to minimize the aggregate regret (or the expected number of mis-classified arms). We prove that our algo…
Algorithm optimizes a single attribute in multi-armed bandits with constraints.
problem Optimizing a single attribute under multiple constraints in multi-armed bandits.
method Successive Rejects framework, information theoretic lower bound.
result Upper bound on probability of error decays exponentially with budget, nearly optimal in certain cases.
Dropout schedules can be optimized to significantly reduce model test loss.
problem Improving model performance in neural networks.
method Developed a mean-field theory of dropout at the edge of chaos, proposing front-loaded dropout schedules.
result Front-loaded dropout schedules reduce test loss by 18-35% over constant dropout.
BCI system improves word selection efficiency using sequential best-arm identification.
problem Conventional non-adaptive BCI paradigms lead to a lengthy learning process.
method Casted as sequence of best-arm identification tasks in multi-armed bandits, using pre-trained LLMs and STTS algorithm.
result Substantial empirical improvement in word selection efficiency demonstrated.
Paper tackles best mixed arm identification with cost constraints in bandit models.
problem Finding the best mixed arm with cost constraints in a stochastic bandit model.
method Proposes SFSR algorithm combining successive reject and score-function-based rejection criteria.
result Upper and lower bounds on mis-identification probability show exponential decay with budget.
We study a specific \textit{combinatorial pure exploration stochastic bandit problem} where the learner aims at finding the set of arms whose means are above a given threshold, up to a given precision, and \textit{for a fixed time horizon}. We propose a parameter-free algorithm based on an original heuristic, and prove…
New strategy optimally identifies best arm in unknown variance Gaussian bandits.
problem Identifying the best arm in two-armed Gaussian bandits with unknown variances.
method Proposes a Neyman Allocation (NA)-Augmented Inverse Probability weighting (AIPW) strategy to estimate variances and draw arms adaptively.
result Demonstrates asymptotic optimality of the proposed strategy in the small-gap regime.
Optimal algorithm for selecting high-quality arms from infinite bandit arms.
problem Efficiently choosing the best arm from an infinite set of options.
method Developed algorithms for both fixed confidence and fixed budget settings, achieving optimal or near-optimal sample complexities.
result Optimal sample complexity results for both fixed confidence and fixed budget settings, resolving open questions in the field.
Proposes rounding method for precise treatment effect estimation under budget constraints.
problem Resource-constrained experimental design for precise treatment effect estimation.
method Dependent randomized rounding procedure to convert assignment probabilities into binary treatment decisions.
result Improved estimator precision through variance reduction and efficient inference.
Crowdsourcing platforms provide marketplaces where task requesters can pay to get labels on their data. Such markets have emerged recently as popular venues for collecting annotations that are crucial in training machine learning models in various applications. However, as jobs are tedious and payments are low, errors …