An optimal algorithm for the Thresholding Bandit Problem

Maurilio Gutzeit · Alexandra Carpentier

68 citations0/0 files storedarXiv (Cornell University)

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Advanced Bandit Algorithms Research Reinforcement Learning in Robotics Optimization and Search Problems

Abstract

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 that it is optimal for this problem by deriving matching upper and lower bounds. To the best of our knowledge, this is the first non-trivial pure exploration setting with \textit{fixed budget} for which optimal strategies are constructed.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 68 citations exist upstream.

References

2002Gambling in a rigged casino: The adversarial multi-armed bandit problem 2009Pure Exploration in Multi-armed Bandits Problems 2002PAC Bounds for Multi-armed Bandit and Markov Decision Processes 2004The Sample Complexity of Exploration in the Multi-Armed Bandit Problem 2013Almost Optimal Exploration in Multi-Armed Bandits 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits

Cited by

2019Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-armed Bandits 2020Gamification of Pure Exploration for Linear Bandits 2019Good arm identification via bandit feedback 2017Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration 2020An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.