We determine the sample complexity of pure exploration bandit problems with multiple good answers. We derive a lower bound using a new game equilibrium argument. We show how continuity and convexity properties of single-answer problems ensures that the Track-and-Stop algorithm has asymptotically optimal sample complexi…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
20 results for “Track-and-Stop”
Develops first optimal algorithm for logistic bandits.
problem Pure exploration in logistic bandits.
method Logistic track-and-stop (Log-TS) algorithm.
result Asymptotically matches lower bound for expected sample complexity.
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…
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.
Contextual information helps identify the best arm more efficiently.
problem Best arm identification with contextual covariate information.
method Proposed a context-aware version of the 'Track-and-Stop' strategy.
result Expected number of arm draws matches lower bound asymptotically.
A new algorithm improves sample complexity for thresholding in Monte Carlo Tree Search.
problem Determining if the root node value of a tree is at least a given threshold.
method Developed a δ-correct sequential sampling algorithm based on the Track-and-Stop strategy.
result Ratio-based modification of D-Tracking strategy reduces sample complexity and computational cost.
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 identifies all ε-optimal arms in a bandit problem with Gaussian rewards.
problem Identifying all ε-optimal arms in a finite stochastic multi-armed bandit with Gaussian rewards.
method The paper provides two lower bounds and a Track-and-Stop strategy to solve the problem, with an efficient numerical method to solve the convex max-min program.
result The Track-and-Stop strategy has asymptotically optimal average sample complexity in the regime of low risk.
Develops a framework for clustering and distribution matching with bandit feedback.
problem Clustering and distribution matching problems with limited feedback.
method General framework using -armed bandit model, Track-and-Stop method, and Frank--Wolfe algorithm.
result Average number of arm pulls matches lower bound, with asymptotic convergence to fundamental limit.
Paper tackles unknown variances in best-arm identification.
problem Identifying the best arm with unknown variances in Gaussian distributions.
method Two approaches: empirical variance plugging or adapting transportation costs.
result The impact of unknown variances is small on sample complexity.
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.
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.
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.
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.
Study on identifying most preferred policy in bandits with vector-valued rewards.
problem Identifying the most preferred policy in bandits with vector-valued rewards.
method Derive a novel lower bound on sample complexity, design the Preference-based Track and Stop (PreTS) algorithm, and derive a new concentration inequality.
result The sample complexity of PreTS is asymptotically tight.
New algorithm finds k-centers from noisy distance estimates.
problem Finding k-centers in unknown metric spaces with noisy distance queries.
method Active algorithms using UCB, Thompson Sampling, and Track-and-Stop.
result Approximation ratio of two with high probability.
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.
New methods for efficient exploration under unknown linear constraints in bandits.
problem Optimizing decisions under unknown linear constraints in bandit problems.
method Lagrangian relaxation, computationally efficient extensions of existing methods, constraint-adaptive stopping rule.
result LAGEX achieves asymptotically optimal sample complexity, LATS shows asymptotic optimality up to novel constants.
Algorithm identifies best policy in MDPs with adaptive sampling.
problem Best policy identification in discounted MDPs with limited samples.
method Derive lower and upper bounds on sample complexity, design KLB-TS algorithm.
result KLB-TS algorithm achieves nearly-optimal sample allocation.
This work introduces CAET, an algorithm for cost-aware pairwise pure exploration.
problem Identifying optimal arm pairs with varying costs in multi-armed bandits.
method Introduces a framework for pairwise pure exploration with arm-specific costs, derives a lower bound, and proposes CAET algorithm.
result CAET optimizes cumulative cost and approaches the lower bound asymptotically.