Simple Bayesian algorithms for best-arm identification
From MaRDI portal
Abstract: This paper considers the optimal adaptive allocation of measurement effort for identifying the best among a finite set of options or designs. An experimenter sequentially chooses designs to measure and observes noisy signals of their quality with the goal of confidently identifying the best design after a small number of measurements. This paper proposes three simple and intuitive Bayesian algorithms for adaptively allocating measurement effort, and formalizes a sense in which these seemingly naive rules are the best possible. One proposal is top-two probability sampling, which computes the two designs with the highest posterior probability of being optimal, and then randomizes to select among these two. One is a variant of top-two sampling which considers not only the probability a design is optimal, but the expected amount by which its quality exceeds that of other designs. The final algorithm is a modified version of Thompson sampling that is tailored for identifying the best design. We prove that these simple algorithms satisfy a sharp optimality property. In a frequentist setting where the true quality of the designs is fixed, one hopes the posterior definitively identifies the optimal design, in the sense that that the posterior probability assigned to the event that some other design is optimal converges to zero as measurements are collected. We show that under the proposed algorithms this convergence occurs at an exponential rate, and the corresponding exponent is the best possible among all allocation
Recommendations
Cites work
- A fully sequential elimination procedure for indifference-zone ranking and selection with tight bounds on probability of correct selection
- A Knowledge-Gradient Policy for Sequential Information Collection
- A Sequential Procedure for Selecting the Population with the Largest Mean from k Normal Populations
- A Single-Sample Multiple Decision Procedure for Ranking Means of Normal Populations with known Variances
- Active sequential hypothesis testing
- Asymptotically efficient adaptive allocation rules
- Asymptotically Optimum Sequential Inference and Design
- Bayesian look ahead one-stage sampling allocations for selection of the best population
- Bayesian statistics and the efficiency and ethics of clinical trials
- Controlled Sensing for Multihypothesis Testing
- Convergence rates of posterior distributions.
- Efficient ranking and selection in parallel computing environments
- Handbook of simulation optimization
- Handbooks in operations research and management science: Simulation
- scientific article; zbMATH DE number 2089367 (Why is no real title available?)
- scientific article; zbMATH DE number 3915462 (Why is no real title available?)
- scientific article; zbMATH DE number 3474804 (Why is no real title available?)
- scientific article; zbMATH DE number 3486880 (Why is no real title available?)
- scientific article; zbMATH DE number 3638998 (Why is no real title available?)
- Indifference-Zone-Free Selection of the Best
- Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
- Learning to optimize via information-directed sampling
- Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges
- On Bayesian index policies for sequential resource allocation
- On the Asymptotic Behavior of Bayes' Estimates in the Discrete Case
- On the complexity of best-arm identification in multi-armed bandit models
- On the consistency of Bayes estimates
- On the convergence rates of expected improvement methods
- On two-stage selection procedures and related probability-inequalities
- Online Network Revenue Management Using Thompson Sampling
- Pure exploration in multi-armed bandits problems
- Second order efficiency in the sequential design of experiments
- Sequential Design of Experiments
- Sequential sampling to myopically maximize the expected value of information
- Simulation budget allocation for further enhancing the efficiency of ordinal optimization
- Stochastically Constrained Ranking and Selection via SCORE
- The center of a system of non-parallel forces
- The consistency of posterior distributions in nonparametric problems
- The knowledge gradient algorithm for a general class of online learning problems
- The sample complexity of exploration in the multi-armed bandit problem
- The Sequential Design of Experiments for Infinitely Many States of Nature
- Thompson sampling: an asymptotically optimal finite-time analysis
Cited in
(18)- Best arm identification in generalized linear bandits
- Nonparametric Bayesian multiarmed bandits for single-cell experiment design
- Dismemberment and design for controlling the replication variance of regret for the multi-armed bandit
- An index-based deterministic convergent optimal algorithm for constrained multi-armed bandit problems
- Learning the distribution with largest mean: two bandit frameworks
- Robust Learning of Consumer Preferences
- Posterior-Based Stopping Rules for Bayesian Ranking-and-Selection Procedures
- Complete expected improvement converges to an optimal budget allocation
- On the finite-sample statistical validity of adaptive fully sequential procedures
- Finding the optimal exploration-exploitation trade-off online through Bayesian risk estimation and minimization
- Using cache or credit for parallel ranking and selection
- Efficient simulation budget allocation for contextual ranking and selection with quadratic models
- Adaptive maximization of social welfare
- Simulation budget allocation for improving scheduling and routing of automated guided vehicles in warehouse management
- Adaptive experiments toward learning treatment effect heterogeneity
- On the problem of best arm retention
- Stochastically constrained best arm identification with Thompson sampling
- On best-arm identification with a fixed budget in non-parametric multi-armed bandits
This page was built for publication: Simple Bayesian algorithms for best-arm identification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144786)
