Timezone: »
Poster
Pure Exploration with Multiple Correct Answers
Rémy Degenne · Wouter Koolen
Wed Dec 11 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #8
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 ensure that the existing Track-and-Stop algorithm has asymptotically optimal sample complexity. However, that convexity is lost when going to the multiple-answer setting. We present a new algorithm which extends Track-and-Stop to the multiple-answer case and has asymptotic sample complexity matching the lower bound.
Author Information
Rémy Degenne (Centrum Wiskunde & Informatica, Amsterdam)
Wouter Koolen (Centrum Wiskunde & Informatica, Amsterdam)
More from the Same Authors
-
2021 : Regret Minimization in Heavy-Tailed Bandits »
Shubhada Agrawal · Sandeep Juneja · Wouter Koolen -
2023 Poster: Fast Asymptotically Optimal Algorithms for Non-Parametric Stochastic Bandits »
Dorian Baudry · Fabien Pesquerel · Rémy Degenne · Odalric-Ambrym Maillard -
2023 Poster: An $\varepsilon$-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond »
Marc Jourdan · Rémy Degenne · Emilie Kaufmann -
2023 Poster: Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games »
Hedi Hadiji · Sarah Sachs · Tim van Erven · Wouter Koolen -
2023 Poster: Non-Asymptotic Analysis of a UCB-based Top Two Algorithm »
Marc Jourdan · Rémy Degenne -
2022 Poster: Top Two Algorithms Revisited »
Marc Jourdan · Rémy Degenne · Dorian Baudry · Rianne de Heide · Emilie Kaufmann -
2022 Poster: Luckiness in Multiscale Online Learning »
Wouter Koolen · Muriel F. Pérez-Ortiz -
2022 Poster: On Elimination Strategies for Bandit Fixed-Confidence Identification »
Andrea Tirinzoni · Rémy Degenne -
2021 Poster: A/B/n Testing with Control in the Presence of Subpopulations »
Yoan Russac · Christina Katsimerou · Dennis Bohle · Olivier Cappé · Aurélien Garivier · Wouter Koolen -
2021 Poster: Optimal Best-Arm Identification Methods for Tail-Risk Measures »
Shubhada Agrawal · Wouter Koolen · Sandeep Juneja -
2019 Poster: Non-Asymptotic Pure Exploration by Solving Games »
Rémy Degenne · Wouter Koolen · Pierre Ménard -
2018 Poster: Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling »
Emilie Kaufmann · Wouter Koolen · Aurélien Garivier -
2017 Poster: Random Permutation Online Isotonic Regression »
Wojciech Kotlowski · Wouter Koolen · Alan Malek -
2017 Poster: Monte-Carlo Tree Search by Best Arm Identification »
Emilie Kaufmann · Wouter Koolen -
2017 Spotlight: Monte-Carlo Tree Search by Best Arm Identification »
Emilie Kaufmann · Wouter Koolen -
2016 Poster: Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning »
Wouter Koolen · Peter Grünwald · Tim van Erven -
2016 Poster: MetaGrad: Multiple Learning Rates in Online Learning »
Tim van Erven · Wouter Koolen -
2016 Oral: MetaGrad: Multiple Learning Rates in Online Learning »
Tim van Erven · Wouter Koolen -
2016 Poster: Combinatorial semi-bandit with known covariance »
Rémy Degenne · Vianney Perchet -
2015 : Discussion Panel »
Tim van Erven · Wouter Koolen · Peter Grünwald · Shai Ben-David · Dylan Foster · Satyen Kale · Gergely Neu -
2015 Workshop: Learning Faster from Easy Data II »
Tim van Erven · Wouter Koolen -
2015 Poster: Minimax Time Series Prediction »
Wouter Koolen · Alan Malek · Peter Bartlett · Yasin Abbasi Yadkori -
2014 Poster: Efficient Minimax Strategies for Square Loss Games »
Wouter M Koolen · Alan Malek · Peter Bartlett -
2014 Poster: Learning the Learning Rate for Prediction with Expert Advice »
Wouter M Koolen · Tim van Erven · Peter Grünwald -
2013 Workshop: Learning Faster From Easy Data »
Peter Grünwald · Wouter M Koolen · Sasha Rakhlin · Nati Srebro · Alekh Agarwal · Karthik Sridharan · Tim van Erven · Sebastien Bubeck -
2013 Workshop: Large Scale Matrix Analysis and Inference »
Reza Zadeh · Gunnar Carlsson · Michael Mahoney · Manfred K. Warmuth · Wouter M Koolen · Nati Srebro · Satyen Kale · Malik Magdon-Ismail · Ashish Goel · Matei A Zaharia · David Woodruff · Ioannis Koutis · Benjamin Recht -
2013 Poster: The Pareto Regret Frontier »
Wouter M Koolen -
2012 Poster: Putting Bayes to sleep »
Wouter M Koolen · Dmitri Adamskiy · Manfred K. Warmuth -
2012 Spotlight: Putting Bayes to sleep »
Wouter M Koolen · Dmitri Adamskiy · Manfred K. Warmuth -
2011 Poster: Adaptive Hedge »
Tim van Erven · Peter Grünwald · Wouter M Koolen · Steven D Rooij -
2011 Poster: Learning Eigenvectors for Free »
Wouter M Koolen · Wojciech Kotlowski · Manfred K. Warmuth