Information Complexity in Bandit Subset Selection

Emilie Kaufmann · Shivaram Kalyanakrishnan

107 citations0/0 files stored

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 Statistical Methods and Inference Game Theory and Voting Systems

Abstract

We consider the problem of efficiently exploring the arms of a stochastic bandit to identify the best subset of a specified size. Under the PAC and the fixed-budget formulations, we derive improved bounds by using KL-divergence-based confidence intervals. Whereas the application of a similar idea in the regret setting has yielded bounds in terms of the KL-divergence between the arms, our bounds in the pure-exploration setting involve the ``Chernoff information'' between the arms. In addition to introducing this novel quantity to the bandits literature, we contribute a comparison between strategies based on uniform and adaptive sampling for pure-exploration problems, finding evidence in favor of the latter.

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 — 107 citations exist upstream.

References

2002Finite-time Analysis of the Multiarmed Bandit Problem 2010Best Arm Identification in Multi-Armed Bandits 2006Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems 2012Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis 2004The Sample Complexity of Exploration in the Multi-Armed Bandit Problem 2013KULLBACK-LEIBLER UPPER CONFIDENCE BOUNDS FOR OPTIMAL SEQUENTIAL ALLOCATION 2010Pure exploration in finitely-armed and continuous-armed bandits 2012PAC Subset Selection in Stochastic Multi-armed Bandits

Cited by

2014Combinatorial Pure Exploration of Multi-Armed Bandits 2014On correlation and budget constraints in model-based bandit optimization with application to automatic machine learning 2014Best-Arm Identification in Linear Bandits 2019Pure Exploration with Multiple Correct Answers 2018Combinatorial Pure Exploration with Continuous and Separable Reward Functions and Its Applications

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.