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.
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…
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.
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…
Optimal best-arm identification with known number of optimal arms.
problem Identifying the best arm in a multi-armed bandit with multiple optimal arms under fixed confidence.
method Deriving a new information-theoretic lower bound and proposing a modified stopping rule.
result Achieving asymptotic instance-optimality with a new lower bound and new stopping rule.
The paper identifies the best treatment to maximize NDPO, a key outcome in causal mediation analysis.
problem Identifying the treatment that maximizes the expected natural direct potential outcome (NDPO) in causal mediation analysis.
method Developed a fixed-confidence best-arm identification (BAI) algorithm based on the Track-and-Stop (TaS) framework, using a cutting-set method to solve a semi-infinite optimization problem.
result The proposed algorithm achieves sample-efficient identification with a high-probability correctness guarantee and asymptotic optimality.
Optimal algorithm for identifying best arm in stochastic linear bandits with fixed confidence.
problem Identifying the best arm in stochastic linear bandits with fixed confidence.
method Extending an algorithm designed for Best Arm Identification to the ε-Thresholding Bandit Problem (TBP). result Asymptotically optimal algorithm for TBP.
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 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.
We consider the problem of near-optimal arm identification in the fixed confidence setting of the infinitely armed bandit problem when nothing is known about the arm reservoir distribution. We (1) introduce a PAC-like framework within which to derive and cast results; (2) derive a sample complexity lower bound for near…
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.
A method identifies abrupt changes in functions with fixed confidence under noisy feedback.
problem Identifying abrupt changes in piecewise constant functions quickly and with certainty.
method Fixed-confidence piecewise constant bandit problem, focusing sampling efforts near change points.
result Asymptotically optimal method proven computationally efficient and effective in experiments.
Optimizes identifying top-k items from comparisons with minimal comparisons.
problem Finding the top-k items from pairwise comparisons with a fixed error rate.
method Developed an asymptotically optimal algorithm using primal-dual procedure and adaptive comparison allocation.
result Proves the algorithm is asymptotically optimal for top-k identification.
We design new algorithms for the combinatorial pure exploration problem in the multi-arm bandit framework. In this problem, we are given K distributions and a collection of subsets V⊂2[K] of these distributions, and we would like to find the subset v∈V that has largest mean, whi…
New algorithms improve stopping time for best arm identification.
problem Efficiently identifying the best alternative in experiments.
method Proposed algorithms with exponential-tailed stopping time.
result Proved that some algorithms never stop, leading to new methods.
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.
We present a new algorithm based on an gradient ascent for a general Active Exploration bandit problem in the fixed confidence setting. This problem encompasses several well studied problems such that the Best Arm Identification or Thresholding Bandits. It consists of a new sampling rule based on an online lazy mirror …
Optimal best arm identification for multi-objective bandits with fixed error probability.
problem Identifying the best arm for each of multiple objectives with fixed confidence.
method Surrogate proportions to sample arms at each time step, eliminating max-min optimisation.
result Asymptotically optimal algorithm for multi-objective best arm identification.
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.
We investigate and provide new insights on the sampling rule called Top-Two Thompson Sampling (TTTS). In particular, we justify its use for fixed-confidence best-arm identification. We further propose a variant of TTTS called Top-Two Transportation Cost (T3C), which disposes of the computational burden of TTTS. As our …
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.
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.
We give a new algorithm for best arm identification in linearly parameterised bandits in the fixed confidence setting. The algorithm generalises the well-known LUCB algorithm of Kalyanakrishnan et al. (2012) by playing an arm which minimises a suitable notion of geometric overlap of the statistical confidence set for t…
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.
Study best arm identification in restless bandits with unknown TPMs.
problem Identify the best arm with fixed confidence in restless bandits with unknown TPMs.
method Proposed a policy for best arm identification and proved its expected stopping time matches the lower bound.
result The state-action visitation proportions match the optimal proportions under any asymptotically optimal policy.
A new strategy for identifying the best arm in Gaussian bandits with improved exploration.
problem Best-arm identification for Gaussian bandits with bounded means and unit variance.
method Exploration-Biased Sampling, a non-asymptotic approach with improved exploration behavior.
result Improved exploration behavior makes the strategy more stable and interpretable.
Fuzzy prediction sets generalize binary predictions to include elements at varying confidence levels.
problem Binary prediction sets are limited; fuzzy prediction sets offer richer guarantees.
method Generalize prediction sets to fuzzy sets, showing they are e-values with merging properties.
result Optimal e-values lead to optimal fuzzy prediction sets, including optimal conformal prediction.
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.
We study an original problem of pure exploration in a strategic bandit model motivated by Monte Carlo Tree Search. It consists in identifying the best action in a game, when the player may sample random outcomes of sequentially chosen pairs of actions. We propose two strategies for the fixed-confidence setting: Maximin…
We give a complete characterization of the sampling complexity of best Markovian arm identification in one-parameter Markovian bandit models. We derive instance specific nonasymptotic and asymptotic lower bounds which generalize those of the IID setting. We analyze the Track-and-Stop strategy, initially proposed for th…
We discuss the coherence properties of Expected Shortfall (ES) as a financial risk measure. This statistic arises in a natural way from the estimation of the "average of the 100p % worst losses" in a sample of returns to a portfolio. Here p is some fixed confidence level. We also compare several alternative representat…
Efficiently clusters noisy data with minimal queries.
problem Clustering elements with noisy oracle feedback.
method Combination of sampling strategy and correlation clustering algorithm.
result First polynomial-time algorithms for NP-hard optimization problem.
The paper tackles multi-armed bandits with vector losses, focusing on minimizing the ℓ∞-norm of relative losses.
problem Minimizing the ℓ∞-norm of relative losses in multi-armed bandits with multiple losses. method Defines relative loss vector, derives lower bounds, and provides matching algorithms for both fixed-confidence best-arm identification and regret minimization.
result Derives problem-dependent sample complexity lower bound and matching algorithms for fixed-confidence best-arm identification.
Optimal algorithms identify non-dominated arms in multi-output linear bandit models.
problem Identifying the Pareto Set in multi-output linear bandit models.
method Design-based algorithms for Pareto Set Identification (PSI) in a structured multi-output linear bandit model.
result Nearly optimal guarantees in both fixed-budget and fixed-confidence settings.
We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the `Track-and-Stop' strategy, which we prove to be asymptotically optimal. It consists in a new sampling rule (which tracks the optim…
The paper tackles identifying Pareto Set with constraints using bandit feedback.
problem Identifying the Pareto Set under feasibility constraints in a multivariate bandit setting.
method Fixed-confidence identification algorithm that outperforms existing methods.
result The sample complexity of the proposed algorithm is near-optimal.
New algorithm reduces sample complexity for planning in MDPs.
problem Planning in MDPs with unknown transitions.
method MDP-GapE, a trajectory-based MCTS algorithm.
result Proves upper bound on sample complexity in terms of sub-optimality gaps.
Study on sample complexity for pure exploration in feedback graph settings.
problem Sample complexity of pure exploration in online learning with feedback graphs.
method Derive instance-specific lower bounds and present asymptotically optimal algorithm TaS-FG.
result TaS-FG is asymptotically optimal and efficient across different graph configurations.
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…
PROBE optimizes best-arm identification with cheap proxies, improving sample complexity.
problem Fixed-confidence best-arm identification with costly rewards and correlated cheap proxies.
method PROBE uses control-variate adjustment and phase elimination to learn residual variance online.
result PROBE achieves oracle sample complexity up to a constant factor and additive calibration cost.
We design and analyze CascadeBAI, an algorithm for finding the best set of K items, also called an arm, within the framework of cascading bandits. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge, namely, that of probabilistically estimating the amount of ava…
Paper proposes Adaptive Pareto Exploration for identifying Pareto optimal arms in multi-objective scenarios.
problem Identifying Pareto optimal arms in multi-objective scenarios with relaxed constraints.
method Adaptive Pareto Exploration strategy for different relaxations of Pareto Set Identification.
result Reduction in sample complexity when identifying at most k Pareto optimal arms.
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.
The paper proposes a novel upper confidence bound (UCB) procedure for identifying the arm with the largest mean in a multi-armed bandit game in the fixed confidence setting using a small number of total samples. The procedure cannot be improved in the sense that the number of samples required to identify the best arm i…
Algorithm identifies best arm in combinatorial bandits with semi-bandit feedback.
problem Identifying the best arm in combinatorial bandits with semi-bandit feedback.
method Interpreted as a sequential zero-sum game, developed a CombGame meta-algorithm with finite time guarantees.
result First computationally efficient algorithm that is asymptotically optimal and has competitive empirical performance.
New algorithms identify best arm with less pulls, adapting to arm covariances.
problem Best arm identification under dependent and correlated arm distributions.
method Adaptive algorithms estimating arm covariances to minimize pulls.
result Substantial improvement in best arm identification over standard setting.
Optimal best-arm identification in linear bandits reduces sampling budget.
problem Identifying the best arm with fixed confidence in stochastic linear bandits.
method A simple algorithm that tracks an optimal proportion of arm draws, updated as rarely as desired.
result The algorithm's sampling complexity matches known lower bounds, asymptotically almost surely and in expectation.
Optimizes pure exploration in linear bandits with a new algorithm.
problem Best-arm identification in linear stochastic bandits.
method Developed the first asymptotically optimal algorithm for fixed-confidence pure exploration in linear bandits.
result Avoids the pitfall of a simple but difficult instance and bypasses the need to solve an optimal design problem.