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.
Algorithm optimizes two objectives in bandits: minimizing regret and identifying best arm.
problem Balancing exploration and exploitation for optimal performance in multi-armed bandits.
method Design and analysis of BoBW-lil'UCB(γ) algorithm, establishing lower bounds. result BoBW-lil'UCB(γ) achieves optimal performance for RM or BAI under different γ values. The paper tackles best arm identification with minimal regret in experiments.
problem Identifying the best arm with minimal regret in experiments.
method Information-theoretic techniques and Double KL-UCB algorithm.
result Achieves asymptotic optimality in identifying the best arm with minimal regret.
New algorithm identifies best target arm with known additive relationship between source and target MAB instances.
problem Identifying the best arm in a target MAB instance when only source arms can be pulled and there's a known additive relationship between the two.
method Proposes an LUCB-style algorithm to identify an ε-optimal target arm with high probability.
result Theoretical analysis highlights aspects of the transfer learning problem and recovers the LUCB algorithm for single domain BAI as a special case.
Optimized Sharpe Ratio for better risk-adjusted decision-making in multi-armed bandits.
problem Challenging to optimize Sharpe Ratio (SR) in multi-armed bandits (MAB) due to constant regret.
method Proposed UCB-RSSR algorithm for RSSR maximization, derived path-dependent concentration bound and regret guarantees.
result UCB-RSSR outperforms existing algorithms and finds applications in risk-aware portfolio management.
A new method for identifying the best arm in multi-armed bandits with mediator feedback.
problem Sequential decision-making with unknown mediator policies.
method Best-arm identification under mediators' feedback (BAI-MF) with statistical lower bound and sequential decision-making strategy.
result The proposed algorithm matches the lower bound on sample complexity for identifying the best arm.
New algorithm for multi-fidelity bandits reduces costs and improves regret.
problem Optimizing decisions with varying costs and accuracy in multi-fidelity bandits.
method Cost complexity bounds, algorithmic framework, elimination-based algorithm.
result New regret definition and matching upper and lower bounds for elimination-based algorithm.
Study on a new family of problems interpolating expert advice and multi-armed bandits.
problem A new family of problems combining expert advice and multi-armed bandits.
method Proved minimax regret bounds and designed optimal PAC algorithms for pure exploration.
result Tight minimax regret bounds and optimal PAC algorithm for m-BAI. TRIPLE efficiently optimizes prompts with a budget constraint.
problem Efficiently selecting good prompts from a pool of candidates.
method TRIPLE connects prompt optimization to best arm identification in MAB, leveraging BAI-FB tools.
result TRIPLE outperforms baselines on multiple tasks with limited budget constraints.
New algorithm for efficiently identifying the best arm in stochastic bandits.
problem Best arm identification in stochastic multi-armed bandits with fixed confidence.
method Sequential probability ratio tests for arm selection.
result Asymptotically optimal sample complexity and guaranteed δ−PAC performance. Algorithm identifies best arm in piecewise stationary linear bandits with minimal samples.
problem Identifying the best arm in a piecewise stationary linear bandit model with unknown contexts and changepoints.
method Design of PSεBAI+ algorithm, consisting of PSεBAI and NεBAI subroutines. result PSεBAI+ achieves optimal sample complexity up to a logarithmic factor. New algorithm identifies best arm efficiently in stochastic bandits.
problem Efficiently identifying the best arm in stochastic bandits with optimal performance.
method Develops a computationally efficient algorithm for optimal best arm identification.
result Achieves optimal performance with minimal computational complexity.
New algorithm identifies best arm in rare event scenarios.
problem Identifying the best arm with tiny reward probability.
method Approximated Compound Poisson process for faster algorithms.
result Improved computational efficiency with minor sample complexity increase.
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.
We consider the quantum version of the bandit problem known as {\em best arm identification} (BAI). We first propose a quantum modeling of the BAI problem, which assumes that both the learning agent and the environment are quantum; we then propose an algorithm based on quantum amplitude amplification to solve BAI. We f…
Improved BAI under DP reduces gap to constant.
problem Fixed-confidence BAI under global DP for Bernoulli distributions.
method New lower bound, stopping rule, and Top Two sampling rule.
result Reduces gap to a small multiplicative constant.
Unified framework for best arm identification and dueling bandits regret minimization.
problem Best arm identification and dueling bandits regret minimization.
method Tree-Guided Identify-Then-Exploit (TG-ITE) framework.
result Unified approach achieving optimal sample complexity and regret guarantees.
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.
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. New algorithm improves best arm identification in Bayesian settings.
problem Finding the arm with the highest mean in unknown distributions.
method Developed a variant of successive elimination algorithm.
result Achieved optimal performance in Bayesian setting with logarithmic gap.
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.
The paper addresses privacy-preserving BAI in clinical trials and user studies.
problem Privacy-preserving Best Arm Identification in adaptive clinical trials and user studies.
method The paper derives lower bounds on sample complexity for BAI algorithms with differential privacy constraints and proposes private variants of Top Two algorithms.
result Private variants of Top Two algorithms achieve asymptotic optimality in terms of sample complexity for BAI problems under differential privacy constraints.
The paper studies privacy-protected BAI with fixed confidence, deriving lower bounds and proposing an adaptive algorithm.
problem Privacy-protected Best Arm Identification (BAI) in data-sensitive applications.
method Derives lower bounds on sample complexity, proposes AdaP-TT algorithm with Laplace noise, and validates with experiments.
result AdaP-TT matches the sample complexity lower bound up to constants in the high-privacy regime.
New bounds derived for KG algorithm's performance in finite time.
problem Best arm identification problem in multi-armed bandit.
method Theoretical analysis of finite-time performance, deriving bounds for sample allocation, error probability, and regret.
result Upper and lower bounds for the probability of error and simple regret of the KG algorithm.
Paper tackles efficient BAI in graph-smooth bandits.
problem Best arm identification with graph smoothness constraint.
method Gradient ascent algorithm for sample complexity.
result Asymptotically optimal strategy for BAI.
Study optimizes identifying the best arm with fixed rounds and Gaussian outcomes.
problem Designing efficient experiments to identify the best arm with fixed rounds and Gaussian outcomes.
method Developed worst-case lower bounds and the GNA-EBA strategy for optimal identification.
result GNA-EBA strategy is asymptotically worst-case optimal.
Experiments in particle physics produce enormous quantities of data that must be analyzed and interpreted by teams of physicists. This analysis is often exploratory, where scientists are unable to enumerate the possible types of signal prior to performing the experiment. Thus, tools for summarizing, clustering, visuali…
New algorithm identifies best arm in semiparametric bandits with near optimal efficiency.
problem Fixed-confidence Best Arm Identification in semiparametric bandits with unknown baseline shift.
method Phase-elimination algorithm based on orthogonalized regression design.
result Nearly optimal high-probability sample-complexity upper bound established.
Study optimal stopping problems with finite-time horizon and proves continuity and strict monotonicity of the boundary.
problem Optimal stopping problems with finite-time horizon and state-dependent discounting.
method Linear diffusion process, time-homogeneous gain function, fine regularity properties, continuity and strict monotonicity proof.
result Proves continuity and strict monotonicity of the optimal stopping boundary under mild assumptions.
Box Thirding identifies the best arm efficiently under limited samples.
problem Efficiently identifying the best arm with limited sampling.
method Iterative ternary comparison of arms, discarding the weakest and exploring the best.
result Achieves comparable performance to Successive Halving with less predefined parameters.
New algorithm identifies best arm in non-stationary linear bandits with improved complexity.
problem Best arm identification in non-stationary linear bandits with adversarial parameters.
method Proposed Adjacent-optimal design and extsfAdjacent−BAI algorithm. result Error probability matches arm-set-dependent lower bound up to constants.
Deep learning model predicts wind-wave relationship.
problem Characterize ocean wave climate for engineering applications.
method Two-stage deep learning model: CNN for spatial features, LSTM for temporal dependencies.
result Predicts spatio-temporal relationship between wind and significant wave height.
Improved knowledge gradient (iKG) outperforms the original KG algorithm in best arm identification problems.
problem Best arm identification (BAI) problem with limitations of the original KG algorithm.
method Follows the one-step look ahead of KG but chooses the measurement that maximizes the probability of selecting the best arm.
result Improved knowledge gradient (iKG) is asymptotically optimal and easier to extend to variant BAI problems.
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.
New dynamic allocation methods for multi-armed bandit models.
problem Dynamic allocation problems in multi-armed bandit models.
method New types of dynamic allocation problems and proofs for Gittins index decomposition.
result New proofs for Gittins index decomposition and related results.
PAC-Bayesian analysis improves lifelong learning in multi-armed bandits.
problem Improving lifelong learning in multi-armed bandits.
method PAC-Bayesian analysis for deriving lower bounds and proposing lifelong learning algorithms.
result Proposed algorithms outperform baseline methods in lifelong multi-armed bandit problems.
The paper explores sampling problems and shows minimal exploration is needed.
problem Exploration-exploitation trade-off in sampling.
method Systematic definition of regret, proposal of a simple algorithm.
result Near-optimal regret bounds achieved with minimal exploration.
Algorithm identifies best arm with biased proxy and selective ground truth audits.
problem Fixed-confidence best-arm identification with biased proxy and selective ground truth.
method Propensity-weighted estimator and adaptive auditing algorithm.
result Plug-in Neyman rule achieves near-oracle audit efficiency.
Paper uses subjective logic to estimate uncertainty in multi-armed bandit problems.
problem Estimating uncertainty in multi-armed bandit problems.
method Formalism of subjective logic applied to multi-armed bandits, proposing new algorithms.
result Subjective logic quantities enable useful assessment of uncertainty.
Proposes an interpretable machine learning framework for multi-arm HTE estimation.
problem Challenges in estimating heterogeneous treatment effects in multi-arm settings.
method Rule-based ensemble approach for HTE estimation in multi-arm trials.
result Achieved lower bias and higher estimation accuracy compared to existing methods.
In this paper we propose a multi-armed bandit inspired, pool based active learning algorithm for the problem of binary classification. By carefully constructing an analogy between active learning and multi-armed bandits, we utilize ideas such as lower confidence bounds, and self-concordant regularization from the multi…
Study finds optimal regret bound for multi-armed bandit problem with expert advice.
problem Optimizing decision-making in a multi-armed bandit problem with expert advice.
method Proved a tight lower bound matching the upper bound of Kale (2014) for minimax expected regret.
result The minimax optimal expected regret is Θ(√(T K log (N/K))) for the problem.
Quantum algorithms for multi-armed bandits are explored with limited reward access.
problem Exploring quantum speed-ups in multi-armed bandit problems with limited reward information.
method Introduced new bandit models and showed query complexity equivalence with classical algorithms.
result No quadratic speed-up is possible for multi-armed bandits with limited reward access.
New policy combines Thompson sampling with best challenger rule for best arm identification.
problem Best arm identification in bandit framework with fixed confidence.
method Combines Thompson sampling with best challenger rule.
result Asymptotically optimal for any two-armed bandit problems, near optimal for general K-armed bandit problems.
Algorithm improves multi-armed bandit performance by transferring reward samples.
problem Sequential multi-armed bandit problem with changing reward distributions.
method UCB algorithm with reward sample transfer.
result Significant improvement in cumulative regret over standard UCB.
New method for identifying best arm in batched multi-armed bandit problems.
problem Identifying the best arm in multi-armed bandit problems where arms are sampled in batches.
method General linear programming framework for best arm identification in batched multi-armed bandit problems.
result Demonstrated good performance in numerical studies compared to UCB-type or Thompson sampling methods.
Study on Pareto optimality in multi-objective bandit problems.
problem Pareto optimality in multi-objective multi-armed bandit problems.
method Formulated adversarial multi-objective multi-armed bandit, defined Pareto regrets, presented algorithms, established upper and lower bounds.
result New algorithms are optimal in adversarial settings and nearly optimal in stochastic settings.
We present a formal model of human decision-making in explore-exploit tasks using the context of multi-armed bandit problems, where the decision-maker must choose among multiple options with uncertain rewards. We address the standard multi-armed bandit problem, the multi-armed bandit problem with transition costs, and …